1. Àü Á¦
Cost¸¦ °®´Â edgeµé¿¡ ´ëÇÑ state space treeÀÇ graph°¡ hamiltonian cycleÀ̶ó¸é,
±× Ãß°¡µÈ edgeµé¿¡ ´ëÇÑ cost¸¦ node·Î ÇÏ´Â graph ¶ÇÇÑ hamiltonian cycleÀÌ´Ù.
2. ±âº» Àü·«
©± ÁÖ¾îÁø Graph¿¡ ´ëÇؼ °¡Àå ³·Àº cost¸¦ °®´Â edge¸¦ Ãß°¡½ÃŲ´Ù.
©² Edge°¡ Ãß°¡µÈ ÈÄ Graph°¡ hamiltonian cycleÀÎÁö¸¦ üũÇÑ´Ù. ´õ ÀÌ»óÀÇ edgeÀÇ Ãß°¡°¡ ¾øÀ¸¸é exitÇÑ´Ù.
©³ Hamiltonian cycleÀ̸é edgeµéÀÇ costÀÇ ÇÕÀ» ÀúÀåÇÑ´Ù. ÀÌ ÀúÀåµÈ °ªÀ» bounding °ªÀ¸·Î ¼³Á¤ÇÏ°í, »õ·Î¿î edgeµéÀÇ cost°¡ À̺¸´Ù Å«Áö¸¦ È®ÀÎÇϸé¼(backtracking) Ãß°¡ÇÑ´Ù. ¸¸¾à, »õ·Î¿î hemiltonian cycle°¡ »ý¼ºµÈ´Ù¸é »õ·Î¿î hemiltonian cycle°¡ °¡Áö°í ÀÖ´Â costÀÇ ÇÕ À» »õ·Î¿î boundingÀÇ °ªÀ» Àç¼³Á¤ÇÑ´Ù.
©´ ©²À» ¹Ýº¹ÇÑ´Ù.
©µ ¸ðµç edgeµéÀÌ visitedµÇ¾úÀ» ¶§, ÀúÀåµÈ graph°¡ hamiltonian cycleÀÌ µÇ°í, Á¾·áÇÑ´Ù.
3. Algorithm
Graph G;
struct EDGE added_edge[N];
int CostSum = 0; /* Graph¿¡ Ãß°¡µÈ edgeµéÀÇ costÀÇ ÇÕ */
struct EDGE Hemil_Cycle; /* Hemiltonian cycle¿¡ ´ëÇÑ Å¸ÀÔ¼³Á¤¡¦(»ý·«)
|