Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีค้นหาแบบค่าทุนน้อยสุด (อังกฤษ: Uniform Cost-Search (UCS)) เป็นการค้นหาโดยใช้ขั้นตอนวิธีแบบแผนภูมิต้นไม้ ใช้สำหรับการแวะผ่านหรือการค้นหาในต้นไม้ค้นหาแบบเทียบน้ำหนัก จากโครงสร้างหรือกราฟ เราจะเริ่มค้นหาจากปมราก ส่วนปมถัดไปที่เราจะเลือกนั้น ต้องทำให้ค่าที่เราสนใจรวมสุทธิจากปมรากไปยังปมนั้นมีค่าทุนน้อยสุด โดยค่าทุนที่เราสนใจนั้นอาจเป็นน้ำหนัก หรือระยะทางก็ได้ เราจะใช้หลักการเลือกแบบนี้จนกว่าจะถึงปมเป้าหมาย
นิยาม
โดยปกติขั้นตอนวิธีการค้นหานั้น จะเกี่ยวข้องกับการสร้างปมลูกโดยการเพิ่มปมข้างเคียงที่ยังไม่มีปมลูกและมีเส้นทางเชื่อมไปยังแถวคอยบุริมภาพ แต่ละปมในแถวคอยจะเก็บค่าทุนสุทธิจากปมราก โดยปมที่มีค่าทุนผ่านทางรวมที่น้อยที่สุดจะเป็นปมในแถวคอยที่มีลำดับความสำคัญมากสุด ปมแรกในแถวคอยจะถูกสร้างลูกเป็นลำดับ โดยจะเพิ่มเซตของปมเชื่อมต่อด้วยค่าทุนรวมจากปมราก UCS นั้นจะเสร็จสมบูรณ์และดีที่สุดเมื่อค่าทุนรวมของแต่ละขั้นตอนเกินค่า ε (ค่าบวก) กรณีที่ใช้เวลาเยอะที่สุดซึ่งมีความซับซ้อนคือ O (b1 + C*/ε) เมื่อ C* คือค่าทุนของผลลัพธ์ที่ดีที่สุด และเมื่อค่าทุนของทุกกรณีเท่ากัน มันจะกลายเป็น O (bd + 1)
รหัสเทียม
- node := root, cost = 0
- frontier := empty priority queue containing node
- explored := empty set
- do
- if frontier is empty
- return failure
- node := frontier.pop ()
- if node is goal
- return solution
- explored.add (node)
- for each of node's neighbors n
- if n is not in explored
- if n is not in frontier
- frontier.add (n)
- if n is in frontier with higher cost
- replace existing node with n
- if n is not in frontier
- if n is not in explored
- if frontier is empty
ขั้นตอนวิธีการที่เกี่ยวข้อง
ขั้นตอนวิธีค้นหาระยะทางแบบเอกรูป เปรียบได้กับการมองBest First Searchแบบง่ายๆ ซึ่งในทางทฤษฎีแล้วก็มีความใกล้เคียงกับDijkstra's Algorithmมากที่สุด และยังเกี่ยวเนื่องกับA* Algorithm
ตัวอย่าง
Expansion showing the explored set and the frontier (priority queue) :
Start Node: A
Goal Node: G
Step 1
Frontier:
| Node | A |
| Cost | 0 |
Explored: -
Step 2
Expand A
Frontier:
| Node | D | B |
| Cost | 3 | 5 |
Explored: A
Step 3
Expand D
Frontier:
| Node | B | E | F |
| Cost | 5 | 5 | 5 |
Explored: A D
Step 4
Expand B
Frontier:
| Node | E | F | C |
| Cost | 5 | 5 | 6 |
Explored: A D B
Step 5
Expand E
Frontier:
| Node | F | C |
| Cost | 5 | 6 |
Explored: A D B E
- Note: B was not added to the priority queue because it was already explored
Step 6
Expand F
Frontier:
| Node | C | G |
| Cost | 6 | 8 |
Explored: A D B E F
Step 7
Expand C
Frontier:
| Node | G |
| Cost | 8 |
Explored: A D B E F C
Step 8
Expand G
Found the path: A to D to F to G
แหล่งข้อมูลที่อ้างอิง
- Uniform cost search - Math Wiki
- Artificial Ingelligence - Uniform Cost Search 2011-08-11 ที่ เวย์แบ็กแมชชีน
- บทความ* 2011-12-26 ที่ เวย์แบ็กแมชชีน
- บทความ** 2012-10-11 ที่ เวย์แบ็กแมชชีน
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud inwithyakarkhxmphiwetxr khntxnwithikhnhaaebbkhathunnxysud xngkvs Uniform Cost Search UCS epnkarkhnhaodyichkhntxnwithiaebbaephnphumitnim ichsahrbkaraewaphanhruxkarkhnhaintnimkhnhaaebbethiybnahnk cakokhrngsranghruxkraf eracaerimkhnhacakpmrak swnpmthdipthieracaeluxknn txngthaihkhathierasnicrwmsuththicakpmrakipyngpmnnmikhathunnxysud odykhathunthierasnicnnxacepnnahnk hruxrayathangkid eracaichhlkkareluxkaebbnicnkwacathungpmepahmayniyamodypktikhntxnwithikarkhnhann caekiywkhxngkbkarsrangpmlukodykarephimpmkhangekhiyngthiyngimmipmlukaelamiesnthangechuxmipyngaethwkhxyburimphaph aetlapminaethwkhxycaekbkhathunsuththicakpmrak odypmthimikhathunphanthangrwmthinxythisudcaepnpminaethwkhxythimiladbkhwamsakhymaksud pmaerkinaethwkhxycathuksranglukepnladb odycaephimestkhxngpmechuxmtxdwykhathunrwmcakpmrak UCS nncaesrcsmburnaeladithisudemuxkhathunrwmkhxngaetlakhntxnekinkha e khabwk krnithiichewlaeyxathisudsungmikhwamsbsxnkhux O b1 C e emux C khuxkhathunkhxngphllphththidithisud aelaemuxkhathunkhxngthukkrniethakn mncaklayepn O bd 1 rhsethiymnode root cost 0 frontier empty priority queue containing node explored empty set doif frontier is emptyreturn failure dd node frontier pop if node is goalreturn solution dd explored add node for each of node s neighbors nif n is not in exploredif n is not in frontierfrontier add n dd if n is in frontier with higher costreplace existing node with n dd dd dd dd khntxnwithikarthiekiywkhxngkhntxnwithikhnharayathangaebbexkrup epriybidkbkarmxngBest First Searchaebbngay sunginthangthvsdiaelwkmikhwamiklekhiyngkbDijkstra s Algorithmmakthisud aelayngekiywenuxngkbA AlgorithmtwxyangExpansion showing the explored set and the frontier priority queue Start Node A Goal Node G Step 1 Frontier Node ACost 0 Explored Step 2 Expand A Frontier Node D BCost 3 5 Explored A Step 3 Expand D Frontier Node B E FCost 5 5 5 Explored A D Step 4 Expand B Frontier Node E F CCost 5 5 6 Explored A D B Step 5 Expand E Frontier Node F CCost 5 6 Explored A D B E Note B was not added to the priority queue because it was already explored dd Step 6 Expand F Frontier Node C GCost 6 8 Explored A D B E F Step 7 Expand C Frontier Node GCost 8 Explored A D B E F C Step 8 Expand G Found the path A to D to F to GaehlngkhxmulthixangxingUniform cost search Math Wiki Artificial Ingelligence Uniform Cost Search 2011 08 11 thi ewyaebkaemchchin bthkhwam 2011 12 26 thi ewyaebkaemchchin bthkhwam 2012 10 11 thi ewyaebkaemchchin