确实对于回路是不可能的，可以很简单的证明出来：假设存在Hamiltonian circuit，那我们可以从图上任意一点出发并回到那一点，不妨设左下角点（1，1）为起始点，那从起始点可以到达的点只有（3，2）或（2，3），既然棋盘对称，不妨设从（1，1）到（3，2），那最终必是（2，3）到（1，1）。同理当考虑经过（5，1）时必是从（3，2）到（5，1）再到（4，3）。以此类推knight只能经过（1，1），（3，2），（5，1），（4，3）…等8个点形成circuit，并非棋盘上所有点都被经过。Contradiction，假设不成立 QED
@@tommymairo8964 Thanks for the explanation. But this is what I consider as "mimicking the behavior of recursion" and very likely slower than recursion solution that compiled on any modern compiler with execution optimization.
@@kingcreo777 It depends on your recursive implementation. If the procedure is tail recursive, it would be absolutely faster, especially when compiler optimizations are enabled. However, if the procedure is not tail recursive, the ret instruction might halt processor's pipeline, which introduces significant overhead. Also, if the non-recursive implementation utilizes deductions and increments on rsp while pushing or popping elements to the search stack, there won't be much pain on performance comparing to recursive solutions.
A knight (chess piece) is placed on field a1 of a chessboard, Is it possible for the knight to make a series of 63 moves (according to chess rules) such that it crosses all the fields of the chessboard and finishes on field h8?
不好意思各位同学，最后留的作业：“在5x5的棋盘上完成闭合的骑士巡游”是不可能的，应该是”在5x5的棋盘上完成开放的骑士巡游路径”，也就是出发点和最后不在一起的骑士巡游路径哈。感谢小朋友给我指出问题，爱你哦～
确实对于回路是不可能的，可以很简单的证明出来：假设存在Hamiltonian circuit，那我们可以从图上任意一点出发并回到那一点，不妨设左下角点（1，1）为起始点，那从起始点可以到达的点只有（3，2）或（2，3），既然棋盘对称，不妨设从（1，1）到（3，2），那最终必是（2，3）到（1，1）。同理当考虑经过（5，1）时必是从（3，2）到（5，1）再到（4，3）。以此类推knight只能经过（1，1），（3，2），（5，1），（4，3）…等8个点形成circuit，并非棋盘上所有点都被经过。Contradiction，假设不成立 QED
難得老師失誤的時候
没事儿，反正我也不做课后作业
我摆了半天，摆不出来可以回到原点。
视频中介绍国际象棋的时候马并没有回到原点啊
很多人說看不懂😂其實這個可以用來規劃旅行路線，如果打算自助旅行，想參觀很多城市，不想重複地點和路線，當然實際上會有機票/車票價格問題，還有每天旅館價格也不同，所以更複雜，旅行除了節省時間，省錢也是挺重要的
旅行为了路费省钱的话更接近的是邮差问题（Chinese postman problem）
@@Cursor42Chinese postman problem 是过每个线，每条路都要走.这个是traveling sellman problem，要到每一个vertices，不一样
@@Cursor42 👍🏻👍🏻我剛剛查了，可以研究一下，讚讚讚
嚴格來說旅行規劃是 CSP 問題，因為要考慮的因素很多。
疫情讓我忘了多久沒去旅行了！😅😅😅
補充李老師的一點，騎士巡邏中，騎士不返回原點（又名開循環）已證明成立，現時未能證明的是騎士巡邏後能返回原點（又名閉循環）成立。
如12:53所示，把多餘路徑拔掉，兩點減1,最後只有兩個1，其他是2,即是可以跳晒所有格不重覆（又名開循環），其實同一筆畫問題雷同，只是需要有系統地清除多餘路徑。所以假設圖是矩形的話，其實勉強可以用M.I.（數學歸納法）*解決問題。（留意路徑，某些點是2,3,4,6...其餘中央全是8）（一筆畫數值總和不可能是單數），開循環已經證明是成立的，只要mxn其中 m,n>4。
更嚴謹的證明是全部都是2，即可以經過所有格而返回原點，這個叫閉循環，這個問題難度大很多，不能單純地堆疊上去,這才是未解決問題。
*先窮舉出5x5,5x6,5x7,5x8,6x6...至7x7,7x8,8x8(共10塊圖）的所有開循環可能性，保留起點和終點1在邊角上的棋譜，若其得出任意兩個1都在邊/角的旁／對面兩點，則可以用M.I堆疊上去，若不則考慮9或以上的數字（但以證明年份來說8x8已經夠用了，9xZ(Z為大於4的整數)在當時電腦能力應該窮舉不了）。而9xZ則自行畫出來配合另一簡單得多的M.I.命題（當m為9時，n>4成立）便可，因5,6,7,8做M.I.已經用突晒。
最近在学图论，学完了，看老师的视频又复习一遍。感谢老师！期待老师的下一次更新！
現實生活是可見的，當考慮運送資源時，一輪車為了節省燃料和時間，必須走遍所有目的地，這理論便套用到行程上。
哪里可以找到模型模拟呢
@@jasonwong264 用電腦編程模擬，再秀出結果，像李老師的棋盤動畫。
不一定的, 除非假設每條通道的成本也相同, 否則因為成本問題, 而有可能走重覆的路.
假設有 3 個目的地 A B C, AB 之間的通道成本 $10, AC 之間成本也是 $10, 但 BC 之間成本 $50.
如果由 A 出發, 先到 B, 再到 C, 成本是 $10 + $50 = $60
但如果由 A 出發, 先到 B, 回到 A, 再到 C, 成本只是 $10 + $10 + $10 = $30
@@jackchung 由於經濟因素，這種情況出現兩個死胡同(懸垂路線)，設計時，即是把$50那條路看作沒有路。
@@jackchung 可以去看看加权有项图
李老师这堂课，除了让我理解了这些学说，还让我深刻理解了所谓广告潜意识催眠大法。
😂😂听着听着，突然好想吃哈密瓜，不知觉的走去冰箱拿起几片啃。
吃飽再說🤣
我想到漢密爾頓手錶
骑士巡游大二的时候做过，extra credit 问题之一，要求非递归解答。当时报电脑专业的学生很多，教授期中考故意给一半人不及格，逼改专业。班里多一半人都drop了。我期中53分，不退。期末考前把所有extra credit 做完，最后拿到A。那节课真的是入门和改专业之间一道坎。
弱弱的问一下，非递归怎么完成骑士巡游DFS？ 模拟栈的这种应该不算吧
感觉我是被劝退的那个😭
@@kingcreo777 每個點有八個方向，依此枚舉。然後把要搜的點壓入棧，每次大循環出棧頂，棧的 FILO 特性保證了與遞歸相似的訪問順序。
@@tommymairo8964 Thanks for the explanation. But this is what I consider as "mimicking the behavior of recursion" and very likely slower than recursion solution that compiled on any modern compiler with execution optimization.
@@kingcreo777 It depends on your recursive implementation. If the procedure is tail recursive, it would be absolutely faster, especially when compiler optimizations are enabled. However, if the procedure is not tail recursive, the ret instruction might halt processor's pipeline, which introduces significant overhead. Also, if the non-recursive implementation utilizes deductions and increments on rsp while pushing or popping elements to the search stack, there won't be much pain on performance comparing to recursive solutions.
老師可以做一期關於玻色愛因斯坦凝聚的視頻嗎？
看著看著又睡著了 謝謝李永樂老師
听到李老师讲这个用来测试计算机专业学生会不会编程时顿感羞愧，我工作五年了，编不出计算骑士巡游问题的程序。
同感，读书时候会的东西工作久了变不会，是不是算很正常😂
如果用遞迴的概念就會很好解決
遞迴程式
穷举回溯其实就能解决了，不过这样的话时间复杂度很高，可以用一些特殊方法剪枝来降低一些复杂度，做性能更好的算法研究的话，估计还得做一些问题转换和进一步优化……(以前好像学过，全忘了。。。)
这个问题一般在上学时期就已经作为作业编过了。但是工作之后忘记了，编不出来很正常，再复习一下就好了。
李永樂老師減肥成功了，而且穿西裝了！比之前有型十倍啊！內容當然還是一如既往的讚！
这不就是本科的专业课《离散数学》嘛
又複習了一次離散和演算法😂😂
论“老师的粉笔前两笔总会断”问题
😂😂要溫柔
以後會請老高專門做一期視頻講解
用羽衣粉笔吧。几年前的趣闻, 美国数学家们曾为之疯狂囤货。
複習應用物理學問題即可求解!
騎士巡遊問題和哈密爾頓問題還是有點區別：哈密爾頓問題不允許一個點被訪問兩次，但是其實巡遊問題允許一個格子被踩兩次。前者確實是 NP-hard，但是後者就變成了求連通分量的個數……
為什麼我們的巡遊問題不一樣
一個格子雖然被踩了兩次 但他在巡遊問題裡被踩的格子是沒有計入點內的
騎士所能到達的格子才是巡遊問題能被訪問的點
把他畫成純幾何圖形或許能讓你比較好理解一點
@@user-de5po8mc1p 這跟計不計入路徑沒關係啊，連通分量用一個並差集就能表示。
期待老师讲一下超弦理论，宇宙万物是不是都是由弦组成，所有力的来源是不是弦振动产生，弦来自哪里？弦为什么能振动？弦振动需要消耗能源吗？
假說這東西老師沒辦法跟你說是不是...就像老師不能跟你說恐龍是不是因為隕石毀滅的一樣
不過我也很好奇老師的見解
看來不是本體論就是第一因問題
如果這是真的，那以後只要演奏一段旋律就能創造一種物質？
@@halrison 弦只是一個拿來解釋粒子的名字 並不是真的那些弦
而且老師是不可能解答的啦
能解答弦理論都能拿十個諾貝爾獎了吧
@@herreraa418 你怎麼知道不是真的弦？
搞不好會像真珠美人魚那樣，唱首歌就能讓對方不舒服啊🤣
大家好，我是四郎，今天给大家带来一局2019五羊杯.................上来走成了中炮对屏风马直车互挺七兵…… 一招！毙命！
走到這，黑方就認輸了
各位棋友，大家好
今天再来介绍一盘气死大爷的棋……🤣🤣🤣
@@user-un3wk6cq8u 你是不是复姓坦白名从宽？
绝杀。。。吴姐！
绝杀----无解！！！
关于最后一个问题：5x5棋盘的骑士巡游。发现如果是从4个顶角处（A_1_1)出发，可以有😃304种巡游路径。而如果是（A_2_1，A_1_2，A_3_1，A_2_3)这类点，没有巡游路径。python code如下：
import numpy as np
import matplotlib.pyplot as plt
import copy
import time
grid_points = []
grid_nom = set()
for i in range(5):
for j in range(5):
grid_nom.add(f"A_{i+1}_{j+1}")
grid_points.append([f"A_{i+1}_{j+1}", i+1, j+1])
origin = "A_2_2"
chain_propogation = [[origin]]
chain_length = 1
grid_num = len(grid_nom)
start = time.time()
while chain_length
@李永乐老师 应该不是您说的1000种？
如果欧拉还在世，这个NP问题我觉得可以转化为P问题，或者可以严谨的证明，无法转化为P问题
No Problem问题，Problem问题（不是
@@ymj5161 啥？？
NP Complete != P. NP Complete证明不难
NPC 問題不複雜，樸素算法很直接。複雜的是如何整一個在多項式時間內能把它搞定的算法……
这个问题复杂到值100万🇺🇸💰😁
我想怎么从来没看过这个，原来是最新的2333 喜欢图论的科普！
马🐎说：又想马儿跑，又想马儿不吃草。
“追日”都够累了，现在还想让我全盘巡逻
马表示：是谁发明「拐马脚」的规则？
人家西洋棋的骑士都没这样🤣🤣🤣
西洋棋比象棋求解简单
@@user-un3wk6cq8u 这只是规则而已吧，我刚学国际象棋的时候对逼和也很不理解，总觉得困毙判负是理所应当的
(尤其和电脑下象棋的时候优势时可以用困毙折磨电脑，因为人类玩家肯定投了。)
讚嘆李永樂老師 期待更多圖論影片
李老师，请问不同的魔方是否也存在哈密尔顿回路？
小朋友准时报道，一般人下棋，不会想到数学问题😂没有想到有两亿多种方法，如果学习多点数学，说不定下棋，玩牌就更厉害了，尤其是麻将，那些高手，一下就胡牌，我这个直脑筋的，根本没有办法比😂
所有的概率游戏的基础都是数学
只有在概率超过50％的情况下
才有可能长（常）玩长赢
不止是麻将，这个逻辑放在
扑克相关的游戏也行
@@user-un3wk6cq8u 還需要有相對大的本金，否則51%勝率還是有可能遇上十連敗就直接破產。
@@Angel-AFA
你說的那種方法
叫做等價鞅策略（martingale ）
這只是理論上可行
一般人相對於賭場是絕對沒有那麼多錢的
要在賭局裡面科學的投注方法
當屬凱利公式
@@user-un3wk6cq8u 我不是在指martingale , 本金分10次去參與遊戲也是可以遇上10連敗破產
我初中的時候曾嘗試想在一個暑假解出，當時還沒有google，長大後才發現當時太無知了
說到圖論又讓我想起葛利恆數
A knight (chess piece) is placed on field a1 of a chessboard,
Is it possible for the knight to make a series of 63 moves
(according to chess rules) such that it crosses all the fields of the chessboard
and finishes on field h8?
李老师瘦了后帅的厉害啊 下次讲讲减肥背后的科学道理吧
老师，可以讲一下p=np难题吗
老师能不能讲讲可乐冰沙机的原理
图论……我很小的时候刚刚学象棋，就想过这个问题……没人和我说过这些……学校的老师也不知道……小县城里的孩子错过了多少
別想太多了，大城市裡的也沒幾個會
一般学计算机、数学相关专业才会学到这个
李老师又开始教图论啦
@李永乐老师 看新闻说费米实验室测定w珀色子超重。能讲下相关知识么？
有趣的內容 李老師還會說愛你喔 。哈哈，有點不適應。
日本將棋 桂馬:哭了 龍馬:喔呵呵，簡單
难办？那就别办了！---就想问问这样排不好座位，乌鸦哥会不会掀桌子
问题是马不是这样走的啊？不是应该走一步再斜过来跳吗？
李老师，这个问题用穷举法亲自去下一下，会不会更有趣
有個數學問題想請教李老師，這是一個很奇特的經驗：昨日老婆帶著五歲的兒子玩，隨手拿了一副舊撲克牌（包含鬼牌），洗牌後本來想由母子各抽一張牌來比大小（不看花色只看數字），結果經過一連六次，母子竟然全都抽出一模一樣的數字（就是母抽到5、兒子也抽到5、母抽到Q，兒子也抽到Q⋯⋯這樣連續6次平手），驚呼不可思議，想知道會出現這樣的機率是多少呢？
大概是三千五百多萬份之一吧
李老师，我以前上学要考试的时候老是上课睡觉，现在工作不考试了老是看你上课，这是为什么
8:50 悬挂人
中国两个数学家发论文据说证明了NP问题，但是现在还没有公认
骑士巡游在8x8棋盘上的解法不是两万亿而是二十六万亿，数量级错了。
您说的对，感谢指正
我很好奇啊，是真的有那种小朋友跟你提问题，还是像我们这样的大龄小朋友？？😶
小朋友你好，你这个问题提的很好👍
李老师脑中有另一个小朋友 ￢ω￢
阁下这个大概是李老师收到过的最差的问题了
剛剛從四郎講象棋一招斃命跳來這裡🤔
笑死
再次被一招斃命
不是太懂，看那个国际象棋棋盘，奇点有8个之多为什么能一笔画？不是2个奇点以上就不行吗？
因為這個問題並不需要走過所有路徑(也就是不需要一筆畫) 也就是它並不是一筆畫問題 而是另一種問題了 自然不能用一筆畫的規則去看待它
@@user-yb7tv8jw6k 噢，是的，明白了，要回去看他的汉密尔顿回路问题。
对文字敏感的我，一开始就发现，李永乐老师写的，周游世界的游字错了。
簡體全部都遊游不分
@@leechan3060 不是一个问题，我是说字最右边（斿-放）写错了，不关乎简繁体偏旁的事
@@john926xayz 喔喔
長芝士了
有个问题，目前点赞的有547人，点踩的有56人，点踩比例很高，这个在李老师的视频里很少见，大家知道是什么原因导致的吗？
怎么看到点踩数的？
@@user-rp6hh1ns1r 一个chrome插件 return youtube dislike
@@LiangLao2 您是啥专业
@@user-om4kn1ep2t 理工科 为什么问这个？
老師可以趕快去畫漫畫嗎？我好想看到庫拉皮卡下船
如果能证明这个问题多项式时间可解话，能拿什么奖？
老师再帮我们复习欧拉定理
这种问题 用计算机编程 轻轻松松
下次面试考考面试者会不会写哈密尔顿回路的算法
馬不停蹄
感谢老师科普
騎士巡邏都難應該在於如何令該路線成閉合路線
卧槽李老师居然讲纯数学问题了
Thanks for sharing
謝分享
今天才知道，原來自己是個”懸掛人“。。。
别是孤立人就好
如果要求不重复走遍每个图中的vertex ， 同时 edge 也不重复， 这个问题有解吗
边本来就不重复的，因为重复走一条边一定会导致重复走过边连接的两个顶点
你是在指边不遗漏吗？凭直觉那样的话相当于一笔画问题且除了起始/终止的每个点的度数只能是2 ，也就是必须是一个没有自相交的链或者环，会变得非常trivial（因为中间的每个点必须是一进一出，所以度数一定是2）。
不会象棋，懵懵懂懂，似懂非懂😅
哈密爾頓？F1車手的姓氏？
吃饭排座，哈哈哈哈好有意思
编程的话用dfs 和backtracking?
那悬挂人以后出去吃饭怎么办？
能，因为我会下象棋，而且很多盘，任何位置马我都跳过。
这不是同一个问题吧，，，不重复是关键
允许重复的话很明显可以，因为只要棋盘足够大马就一定能跳到所有邻格
不能啊
棋盤上剩一匹馬
沒有將帥比賽早結束了
很显然有些数学家平时吃得太饱了
直接dfs 或者bfs
小朋友够用吗
）什麽叫做壞事？這就叫做壞事。（同曰恶？此所谓为不善也。）如果朱霞說的不對，則其可以道歉和改口，但是你不能不允許人說話。（若霞之言非也，则可以谢改，而不能不许。）當年陳毅就開小會說你所認賊作父的那個父、搞一言堂欺負臣僚們嘛--（毅乃开小会曰残君所识父，作堂欺群臣--）你再這樣下去，你可能會完蛋。（君再继之以固，則覆巢之下，汝其全卵？！）
感謝老師 無私分享知識 總比留到死來的好
有意思
这个问题我学会之后，我送外卖速度更快了
那国际象棋呢？
好难，纯顶👍
马走日原来是这样来的
我去，OI人狂喜😎
骑士别巡游了 老将被将军了
哇，讲图论了。有好多东西可以讲了
粉笔质量有问题。
Holyshit I still able to understand something in this advance math in Chinese wtf is wrong with me.
凭经验判断能
哈密瓜
头秃系列🤣😂
第一笔就断粉笔了，草
写一个DFS可解
知其然了
图论问题没什么好的解决方法，一边都是用编程软件，效率比较高，图论问题应用面非常广
我有選修算幾數學
好的解決方案是有的吧
對於數感要求蠻高的
小時候總覺得那些老師好無聊，整天講些毫無意義的問題，現實中完全不可能遇到
实话实说我不懂下象棋😁😁
🙃
看開頭和結尾
這到底在說啥呢?..........不懂...🤣
開頭不懂,結尾也不懂😂
看结尾也没看出明确答案，马说：我只是个引子
来嘛，谁来解决一下P=NP，全世界都会谢谢你
西洋象棋的子是放格子，而中国象棋的子是放在点上。是不是应该先说明什么，要不然会很怪！
其实没有区别的，格子也可以简化成一个点
抱歉……我觉得研究这个问题好无聊……
悬挂人 生草
❤️🌟近年來災禍頻繁，異象頻現，大家必須認罪悔改，希望還未信靠耶穌和神的人盡快信靠耶穌和神，盡快認罪悔改。2000前光來到了世上，耶穌基督來到了世上，道成了肉身顯現在世人的眼前，祂為世人的罪被釘死在十字架上，第三日祂復活了，然後祂升天了，坐在神的右邊。如果你真心誠意信靠耶穌基督並接受祂為你生命的救主，你就領受聖靈了，然後，你必須順從聖靈，依靠聖靈的引導去行事為人，做一個神所喜悅的人。
聖靈所結的果子，就是仁愛、喜樂、和平、忍耐、恩慈、良善、信實、溫柔、節制，這樣的事沒有律法禁止。-加拉太書 5:22-23
不要耽延，你應該立刻信靠耶穌基督與神!
硬