哈密頓迴路問題（Hamilton cycle problem）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：哈密頓迴路問題
- 外文名：Hamilton cycle problem
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
對任意給定的圖 G，判定是否存在G的一條路徑，它經過G 中每一個節點恰好一次。
出處
《計算機科學技術名詞 》第三版。
哈密頓迴路問題
相關詞條
- 哈密頓迴路問題
哈密頓迴路問題（Hamilton cycle problem）是2018年公布的計算機科學技術名詞。定義對任意給定的圖 G，判定是否存在G的一條路徑，它經過G 中每一個節點恰好一次。出處《計算機科學技術名詞 》第三版。1...
- 哈密頓迴路
哈密頓圖（哈密爾頓圖）（英語：Hamiltonian graph，或Traceable graph）是一個無向圖，由天文學家哈密頓提出，由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。在圖論中是指含有哈密頓迴路的圖，閉合的哈密頓路徑稱作哈密...
- 哈密頓圈問題
哈密頓圈問題(Hamilton circuit problem)是圖論中著名的難題之一。巡迴售貨員問題有一個基於圖的天然類似問題，它是圖論中的一個基本問題，給定一個有向圖G(V，E)，如果G中的圈C恰好經過每一個頂點一次，則稱圈C是一個哈密頓圈。...
- 哈密頓圖
推論： n(n≥3)階有向完全圖為哈密頓圖。哈密頓路徑也稱作哈密頓鏈，指在一個圖中沿邊訪問每個頂點恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完全(NP-complete）問題。後來人們也證明了，找一條哈密頓路的近似比為常數的...
- 迷茫的旅行商 : 一個無處不在的計算機算法問題
9.3 Cook定理和Karp問題列表 196 9.3.1 複雜性類 196 9.3.2 問題歸約 198 9.3.3 21個NP完全問題 199 9.3.4 百萬美金 200 9.4 TSP研究現狀 200 9.4.1 哈密頓迴路 201 9.4.2 幾何問題 ...
- 馬踏棋盤
馬踏棋盤問題是旅行商問題（TSP）或哈密頓迴路問題（HCP）的一個特例。在 8×8 的西洋棋棋盤上，用一個馬按照馬步跳遍整個棋盤，要求每個格子都只跳到一次，最後回到出發點。這是一個 NP問題，通常採用回溯法或啟發式搜尋類算法...
- 塔特猜想
表面上看哈密頓圖的概念與歐拉圖的概念非常相似，但兩者迥然不同。可以找到一個歐拉圖但不是哈密頓圖的例子，也可以找到一個哈密頓圖但不是歐拉圖的例子。對哈密頓圖的判定問題，迄今還沒有像歐拉圖那樣能找到一個很漂亮的充分必要...
- 楊元生(大連理工大學計算機系教授)
（6）哈密頓迴路問題也是圖論的一個相當活躍的分支。我們研製出在有向圖中尋找哈密頓迴路的快速回溯法,該算法對稀疏圖尤其有效。南斯拉夫數學家Bernardo Recaman 猜想，當n32 時，平方圖(若且唯若圖上兩點的編號和為平方數時，該...
- DNA計算
1994年，美國加利福尼亞大學的Adleman博士在《科學》期刊上首次發表了關於DNA分子生物計算方法的開創性文章，他通過生化方法求解了7個頂點的哈密頓迴路問題，顯示了用DNA進行特定目的計算的可行性，其新穎性不僅僅在於算法，也不僅僅在於速度...
- 好玩的數學·幻方及其他:娛樂數學經典名題
第十四章 棋盤上的哈密頓迴路 問題的提出 馬步哈密頓迴路的歐拉解法·內外分層法求哈密頓迴路·羅傑特的巧妙方法 幾個有特色的馬步哈密頓迴路 棋盤上的不解之謎 習題 第十五章 八皇后問題 八皇后問題的起源與解 小棋盤上的皇后問題 ...
- 近似算法
旅行售貨員問題近似算法 問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。旅行售貨員問題的一些特殊性質：比如，費用函式c往往具有三角不等式性質，即對任意的...
- JavaEE輕量級框架Struts2+Spring+Hibernate整合開發
3.2.2串匹配問題37 3.3排序問題中的蠻力法42 3.3.1選擇排序42 3.3.2起泡排序43 3.4組合問題中的蠻力法44 3.4.10/1背包問題44 3.4.2任務分配問題45 3.5圖問題中的蠻力法46 3.5.1哈密頓迴路問題46 3.5.2TSP問題47...
- 深度優先回溯
這種方法適用於解的組合數相當大但仍然有限的那一類問題，例如八皇后問題、圖的著色問題、哈密頓迴路問題等。一些軟體系統也採用回溯法。回溯法通常用最簡單的遞歸方法來實現，可能出現兩種情況：找到一個可能存在的正確的答案；在嘗試了...
- Introduction to Algorithms
34．5 np完全問題 34．5．1 團問題 34．5．2 頂點覆蓋問題 34．5．3 哈密頓迴路問題 34．5．4 旅行商問題 34．5．5 子集和問題 第35章 近似算法 35．1 頂點覆蓋問題 35．2 旅行商問題 35．2．1 滿足三角不等式的旅行商...
- 算法基礎(第5版)
5.2 n皇后問題 129 5.3 用蒙特卡洛算法估計回溯算法的效率 132 5.4 “子集之和”問題 134 5.5 圖的著色 138 5.6 哈密頓迴路問題 141 5.7 0-1背包問題 143 5.7.1 0-1背包問題的回溯算法 143 5.7.2 比較0-1背包...
- 計算機導論(第4版)(微課版)
8.5小結 拓展閱讀： 吳文俊和定理的自動證明 習題 思考題 第9章計算機領域的典型問題 9.1圖論問題 9.1.1哥尼斯堡七橋問題 9.1.2哈密頓迴路問題 9.1.3中國郵路問題 9.2算法複雜性問題 9.2.1漢諾塔問題 9.2.2旅行商問題 ...
- 算法設計與分析基礎(第3版)
11.3.1 P和NP問題 308 11.3.2 NP完全問題 311 習題11.3 314 11.4 數值算法的挑戰 316 習題11.4 322 小結 323 第12章 超越算法能力的極限 325 12.1 回溯法 325 12.1.1 n皇后問題 326 12.1.2 哈密頓迴路問題 ...
- 算法設計與分析(第3版)(2023年清華大學出版社出版的圖書)
9.2.3CookLevin定理——第一個NP完全問題239 9.3幾個NP完全問題239 9.3.1最大可滿足性與三元可滿足性239 9.3.2頂點覆蓋、團與獨立集241 9.3.3哈密頓迴路與貨郎問題243 9.3.4恰好覆蓋245 9.3.5子集和、背包、裝箱與...
- 幻方及其他
第十四章 棋盤上的哈密頓迴路 第十五章 八皇后問題 第十六章 數字啞謎——有趣的算式復員問題 第十七章 數學王國中的金字塔 第十八章 誰是倖存者 第十九章 變化無窮的雙人取物遊戲 第二十章 關於重排九宮 第二十一章 梵塔問題透視...
- 算法設計與分析基礎第二版
11.3 P、NP和NP完全問題 11.3.1 P和NP問題 11.3.2 NP完全問題 習題11.3 11.4 數值算法的挑戰 習題11.4 小結 第12章 超越算法能力的極限 12.1 回溯法 12.1.1 n皇后問題 12.1.2 哈密頓迴路問題 12.1.3 子集和問題...
- 離散數學及套用(第2版)
A.12 中國郵路問題 417 A.13 格雷碼、超立方體的哈密頓迴路和九連環 420 A.13.1 格雷碼 420 A.13.2 超立方體圖中的哈密頓迴路 421 A.13.3 九連環與格雷碼 423 A.14 謝爾賓斯基三角 426 附錄B?課程綜合實驗??/ 433 B.1 ...
- 算法設計與分析第二版
3.1 多項式時間變換 8.3.2 Cook定理 8.4 一些典型的NP完全問題 8.4.1 合取範式的可滿足性問題 8.4.2 3元合取範式的可滿足性問題 8.4.3 團問題 8.4.4 頂點覆蓋問題 8.4.5 子集和問題 8.4.6 哈密頓迴路問題 ……
- 幻方及其他 : 娛樂數學經典名題 | 2版
第二部分是娛樂數學其他經典名題，包括數字啞謎、數學金字塔、素數、完美數、自守數、累進可除數，以及“數學黑洞”現象、棋盤上的哈密頓迴路、八皇后問題、梵塔、重排九宮等問題。圖書目錄 總序 第二版修訂本說明 第二版說明 前言 第一...
