title: "[Algorithm] Back-Tracking & IDDFS" date: 2022-04-12 21:15:00 tags:
{% raw %}
<h1>Backtracking</h1>
<h2>Integer Transformation Problem</h2>
<h3>Description</h3>
<p>整数变换问题。关于整数 i 的变换 f 和 g 定义如下：f(i)=3i；g(i)=i/2 (向下取整)。 试设计一个算法，对于给定的 2 个整数 n 和 m，用最少的 f 和 g 变换次数将 n 变换为 m。 例如，可以将整数 15 用 4 次变换将它变换为整数 4：4=gfgg(15)。当整数 n 不可能变换 为整数 m 时，算法应如何处理?</p> <h3>Input</h3> <p>由文件 input.txt 给出输入数据。第一行有 2 个正整数 n 和 m。</p> <h3>Output</h3> <p>将计算出的最少变换次数以及相应的变换序列输出到文件 output.txt。文件的第一行是 最少变换次数。文件的第 2 行是相应的变换序列。</p> <h3>Sample</h3> <p><strong>输入文件示例</strong></p> <p>input.txt</p> <p>15 4</p> <p><strong>输出文件示例</strong></p> <p>output.txt 4 gfgg</p> <h3>Analysis</h3> <h4>DFS</h4> <p>定义 <code>转变函数 (Transformation Function)</code> <mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="4.299ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 1900 1000" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.566ex;"><defs><path id="MJX-19-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-19-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-19-TEX-I-1D465" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path id="MJX-19-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-19-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(550,0)"><use data-c="28" xlink:href="#MJX-19-TEX-N-28"></use></g><g data-mml-node="mi" transform="translate(939,0)"><use data-c="1D465" xlink:href="#MJX-19-TEX-I-1D465"></use></g><g data-mml-node="mo" transform="translate(1511,0)"><use data-c="29" xlink:href="#MJX-19-TEX-N-29"></use></g></g></g></svg></mjx-container><script type="math/tex">f(x)</script> 和 <mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="4.133ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 1827 1000" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.566ex;"><defs><path id="MJX-20-TEX-I-1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path><path id="MJX-20-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-20-TEX-I-1D465" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path id="MJX-20-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D454" xlink:href="#MJX-20-TEX-I-1D454"></use></g><g data-mml-node="mo" transform="translate(477,0)"><use data-c="28" xlink:href="#MJX-20-TEX-N-28"></use></g><g data-mml-node="mi" transform="translate(866,0)"><use data-c="1D465" xlink:href="#MJX-20-TEX-I-1D465"></use></g><g data-mml-node="mo" transform="translate(1438,0)"><use data-c="29" xlink:href="#MJX-20-TEX-N-29"></use></g></g></g></svg></mjx-container><script type="math/tex">g(x)</script></p> <p>由于需要求出，对于给定输入<code>整数n</code>，是否可以 <code>某种转变函数序列</code>来 <code>转变</code>到 <code>整数m</code></p> <p>我们不妨首先考虑使用 <code>Brute-Force Method</code>来处理该问题。</p> <p>因为存在2种转变方式，所以我们定义的递归是 <code>2路递归</code>。</p> <blockquote><p>换句话说，这个 <code>递归方法</code>产生的 <code>解空间树</code>是一颗 <code>二叉树</code></p> </blockquote> <p>同时，我们通过题意可知，<code>递归次数的下界</code>为 <code>0</code>，但 <code>递归次数的上界</code>未知。</p> <p>我们做一个 <code>猜测</code>：如果 <code>递归次数</code>超过 <code>整数n</code>，则 <code>不太可能</code> 存在解。</p> <p>于是，对于该方法，我们会按照 <code>深度优先搜索</code>的顺序来访问 <code>解空间树</code></p> <blockquote><p>假设我们已知拥有了 <code>整颗解空间树 (二叉树)</code>。则实际上，我们会直观地发现，</p> <p>我们会从 <code>树根</code>节点开始，沿着一条 <code>路径</code>做 <code>深度搜索</code>，直到抵达 <code>我们设定的最大层次 （也就是我们预测的递归次数的上界）</code>，再进行 <code>回溯</code>。（这个过程产生的方案是：<mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="39.035ex" height="5.585ex" role="img" focusable="false" viewBox="0 -705 17253.5 2468.8" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -3.99ex;"><defs><path id="MJX-15-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-15-TEX-N-2192" d="M56 237T56 250T70 270H835Q719 357 692 493Q692 494 692 496T691 499Q691 511 708 511H711Q720 511 723 510T729 506T732 497T735 481T743 456Q765 389 816 336T935 261Q944 258 944 250Q944 244 939 241T915 231T877 212Q836 186 806 152T761 85T740 35T732 4Q730 -6 727 -8T711 -11Q691 -11 691 0Q691 7 696 25Q728 151 835 230H70Q56 237 56 250Z"></path><path id="MJX-15-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path><path id="MJX-15-TEX-S4-E152" d="M-24 327L-18 333H-1Q11 333 15 333T22 329T27 322T35 308T54 284Q115 203 225 162T441 120Q454 120 457 117T460 95V60V28Q460 8 457 4T442 0Q355 0 260 36Q75 118 -16 278L-24 292V327Z"></path><path id="MJX-15-TEX-S4-E153" d="M-10 60V95Q-10 113 -7 116T9 120Q151 120 250 171T396 284Q404 293 412 305T424 324T431 331Q433 333 451 333H468L474 327V292L466 278Q375 118 190 36Q95 0 8 0Q-5 0 -7 3T-10 24V60Z"></path><path id="MJX-15-TEX-S4-E151" d="M-10 60Q-10 104 -10 111T-5 118Q-1 120 10 120Q96 120 190 84Q375 2 466 -158L474 -172V-207L468 -213H451H447Q437 -213 434 -213T428 -209T423 -202T414 -187T396 -163Q331 -82 224 -41T9 0Q-4 0 -7 3T-10 25V60Z"></path><path id="MJX-15-TEX-S4-E150" d="M-18 -213L-24 -207V-172L-16 -158Q75 2 260 84Q334 113 415 119Q418 119 427 119T440 120Q454 120 457 117T460 98V60V25Q460 7 457 4T441 0Q308 0 193 -55T25 -205Q21 -211 18 -212T-1 -213H-18Z"></path><path id="MJX-15-TEX-S4-E154" d="M-10 0V120H410V0H-10Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(827.8,0)"><use data-c="2192" xlink:href="#MJX-15-TEX-N-2192"></use></g><g data-mml-node="mi" transform="translate(2105.6,0)"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(2655.6,0)"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(3483.3,0)"><use data-c="2192" xlink:href="#MJX-15-TEX-N-2192"></use></g><g data-mml-node="mi" transform="translate(4761.1,0)"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(5311.1,0)"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(5861.1,0)"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(6577.8,0)"><use data-c="22EF" xlink:href="#MJX-15-TEX-N-22EF"></use></g><g data-mml-node="mo" transform="translate(8027.6,0)"><use data-c="2192" xlink:href="#MJX-15-TEX-N-2192"></use></g><g data-mml-node="munder" transform="translate(9305.3,0)"><g data-mml-node="TeXAtom" data-mjx-texclass="OP" transform="translate(2671.4,0)"><g data-mml-node="munder"><g data-mml-node="mrow"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(716.7,0)"><use data-c="22EF" xlink:href="#MJX-15-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(2055.3,0)"><use data-c="1D453" xlink:href="#MJX-15-TEX-I-1D453"></use></g></g><g data-mml-node="mo" transform="translate(0,-630)"><use data-c="E152" xlink:href="#MJX-15-TEX-S4-E152"></use><use data-c="E153" xlink:href="#MJX-15-TEX-S4-E153" transform="translate(2155.3,0)"></use><g data-c="E156" transform="translate(852.7,0)"><use data-c="E151" xlink:href="#MJX-15-TEX-S4-E151"></use><use data-c="E150" xlink:href="#MJX-15-TEX-S4-E150" transform="translate(450,0)"></use></g><svg width="602.7" height="720" x="350" y="-300" viewBox="150.7 -300 602.7 720"><use data-c="E154" xlink:href="#MJX-15-TEX-S4-E154" transform="scale(2.26,1)"></use></svg><svg width="602.7" height="720" x="1652.7" y="-300" viewBox="150.7 -300 602.7 720"><use data-c="E154" xlink:href="#MJX-15-TEX-S4-E154" transform="scale(2.26,1)"></use></svg></g></g></g><g data-mml-node="TeXAtom" transform="translate(0,-1522.3) scale(0.707)" data-mjx-texclass="ORD"><g data-mml-node="mtext"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">我</text></g><g data-mml-node="mtext" transform="translate(980.8,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">们</text></g><g data-mml-node="mtext" transform="translate(1916.4,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">设</text></g><g data-mml-node="mtext" transform="translate(2845.6,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">定</text></g><g data-mml-node="mtext" transform="translate(3781.2,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">的</text></g><g data-mml-node="mtext" transform="translate(4665.2,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">递</text></g><g data-mml-node="mtext" transform="translate(5646,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">归</text></g><g data-mml-node="mtext" transform="translate(6530,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">的</text></g><g data-mml-node="mtext" transform="translate(7414,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">最</text></g><g data-mml-node="mtext" transform="translate(8394.8,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">大</text></g><g data-mml-node="mtext" transform="translate(9375.6,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">深</text></g><g data-mml-node="mtext" transform="translate(10304.7,0)"><text data-variant="normal" transform="scale(1,-1)" font-size="884px" font-family="serif">度</text></g></g></g></g></g></svg></mjx-container><script type="math/tex">f \rightarrow ff \rightarrow fff \cdots \rightarrow \underbrace{f\cdots f}_{我们设定的递归的最大深度}</script></p> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:pink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:pink,stroke:#333,stroke-width:4px f --> fg((g)); g --> gf((f)); g --> gg((g)); ff --> fff((f)); style fff fill:pink,stroke:#333,stroke-width:4px ff --> ffg((g)); fg --> fgf((f)); fg --> fgg((g)); gf --> gff((f)); gf --> gfg((g)); gg --> ggf((f)); gg --> ggg((g)); fff --> ffff((f)); style ffff fill:pink,stroke:#333,stroke-width:4px fff --> fffg((g)); ffg --> ffgf((f)); ffg --> ffgg((g)); fgf --> fgff((f)); fgf --> fgfg((g)); fgg --> fggf((f)); fgg --> fggg((g)); gff --> gfff((f)); gff --> gffg((g)); gfg --> gfgf((f)); gfg --> gfgg((g)); ggf --> ggff((f)); ggf --> ggfg((g)); ggg --> gggf((f)); ggg --> gggg((g)); </code></pre> <blockquote><p>当然，如果说，在 <code>沿着当前路径</code> <code>抵达人为设定的递归的最大深度</code>之前，我们 <code>幸运地</code>发现，已经找到了 <code>解</code>。</p> <blockquote><p>但是请注意：这个 <code>解</code>并不一定是 <code>最优解</code>，因为我们实际上进行的是 <code>深度优先搜索</code>。</p> <p><code>这个解</code>只不过是 <code>当前搜索路径</code>上的 <code>最优解</code>：因为在 <code>当前搜索路径</code>上，<code>该解</code>是 <code>第一个被发现的解</code>。</p> <p>根据题目的性质，我们可以知道，<code>在该条路径上的后续发现的解</code> 并不会 <code>优于</code> <code>在该条路径上被发现的第一个解</code>。</p> </blockquote> </blockquote> <p>如果，我们 <code>十分不幸运</code>，在 <code>沿着该条深度优先搜索路径</code> <code>抵达我们人为设定的最大递归深度</code>时，仍然 <code>未发现解</code>，</p> <p>则此时我们方法会见 <code>回溯1步</code>：<mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="20.12ex" height="2.059ex" role="img" focusable="false" viewBox="0 -705 8893.2 910" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.464ex;"><defs><path id="MJX-16-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-16-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path><path id="MJX-16-TEX-N-2192" d="M56 237T56 250T70 270H835Q719 357 692 493Q692 494 692 496T691 499Q691 511 708 511H711Q720 511 723 510T729 506T732 497T735 481T743 456Q765 389 816 336T935 261Q944 258 944 250Q944 244 939 241T915 231T877 212Q836 186 806 152T761 85T740 35T732 4Q730 -6 727 -8T711 -11Q691 -11 691 0Q691 7 696 25Q728 151 835 230H70Q56 237 56 250Z"></path><path id="MJX-16-TEX-I-1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(716.7,0)"><use data-c="22EF" xlink:href="#MJX-16-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(2055.3,0)"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(2605.3,0)"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(3155.3,0)"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(3983.1,0)"><use data-c="2192" xlink:href="#MJX-16-TEX-N-2192"></use></g><g data-mml-node="mi" transform="translate(5260.9,0)"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(5977.6,0)"><use data-c="22EF" xlink:href="#MJX-16-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(7316.2,0)"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(7866.2,0)"><use data-c="1D453" xlink:href="#MJX-16-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(8416.2,0)"><use data-c="1D454" xlink:href="#MJX-16-TEX-I-1D454"></use></g></g></g></svg></mjx-container><script type="math/tex">f\cdots fff \rightarrow f \cdots ffg</script></p> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:pink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:pink,stroke:#333,stroke-width:4px f --> fg((g)); g --> gf((f)); g --> gg((g)); ff --> fff((f)); style fff fill:pink,stroke:#333,stroke-width:4px ff --> ffg((g)); fg --> fgf((f)); fg --> fgg((g)); gf --> gff((f)); gf --> gfg((g)); gg --> ggf((f)); gg --> ggg((g)); fff --> ffff((f)); fff --> fffg((g)); style fffg fill:pink,stroke:#333,stroke-width:4px ffg --> ffgf((f)); ffg --> ffgg((g)); fgf --> fgff((f)); fgf --> fgfg((g)); fgg --> fggf((f)); fgg --> fggg((g)); gff --> gfff((f)); gff --> gffg((g)); gfg --> gfgf((f)); gfg --> gfgg((g)); ggf --> ggff((f)); ggf --> ggfg((g)); ggg --> gggf((f)); ggg --> gggg((g)); </code></pre> <p> </p> <p>如果此时还 <code>未发现解</code>，则 <code>再回溯1步</code>：<mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="19.955ex" height="2.059ex" role="img" focusable="false" viewBox="0 -705 8820.2 910" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.464ex;"><defs><path id="MJX-17-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-17-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path><path id="MJX-17-TEX-I-1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path><path id="MJX-17-TEX-N-2192" d="M56 237T56 250T70 270H835Q719 357 692 493Q692 494 692 496T691 499Q691 511 708 511H711Q720 511 723 510T729 506T732 497T735 481T743 456Q765 389 816 336T935 261Q944 258 944 250Q944 244 939 241T915 231T877 212Q836 186 806 152T761 85T740 35T732 4Q730 -6 727 -8T711 -11Q691 -11 691 0Q691 7 696 25Q728 151 835 230H70Q56 237 56 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-17-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(716.7,0)"><use data-c="22EF" xlink:href="#MJX-17-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(2055.3,0)"><use data-c="1D453" xlink:href="#MJX-17-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(2605.3,0)"><use data-c="1D453" xlink:href="#MJX-17-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(3155.3,0)"><use data-c="1D454" xlink:href="#MJX-17-TEX-I-1D454"></use></g><g data-mml-node="mo" transform="translate(3910.1,0)"><use data-c="2192" xlink:href="#MJX-17-TEX-N-2192"></use></g><g data-mml-node="mi" transform="translate(5187.9,0)"><use data-c="1D453" xlink:href="#MJX-17-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(5904.6,0)"><use data-c="22EF" xlink:href="#MJX-17-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(7243.2,0)"><use data-c="1D453" xlink:href="#MJX-17-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(7793.2,0)"><use data-c="1D454" xlink:href="#MJX-17-TEX-I-1D454"></use></g><g data-mml-node="mi" transform="translate(8270.2,0)"><use data-c="1D453" xlink:href="#MJX-17-TEX-I-1D453"></use></g></g></g></svg></mjx-container><script type="math/tex">f\cdots ffg \rightarrow f\cdots fgf</script></p> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:pink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:pink,stroke:#333,stroke-width:4px f --> fg((g)); g --> gf((f)); g --> gg((g)); ff --> fff((f)); ff --> ffg((g)); style ffg fill:pink,stroke:#333,stroke-width:4px fg --> fgf((f)); fg --> fgg((g)); gf --> gff((f)); gf --> gfg((g)); gg --> ggf((f)); gg --> ggg((g)); fff --> ffff((f)); fff --> fffg((g)); ffg --> ffgf((f)); style ffgf fill:pink,stroke:#333,stroke-width:4px ffg --> ffgg((g)); fgf --> fgff((f)); fgf --> fgfg((g)); fgg --> fggf((f)); fgg --> fggg((g)); gff --> gfff((f)); gff --> gffg((g)); gfg --> gfgf((f)); gfg --> gfgg((g)); ggf --> ggff((f)); ggf --> ggfg((g)); ggg --> gggf((f)); ggg --> gggg((g)); </code></pre> <p>如果仍然 <code>未发现解</code>，则 <code>再回溯一步</code>： <mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="19.79ex" height="2.059ex" role="img" focusable="false" viewBox="0 -705 8747.2 910" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.464ex;"><defs><path id="MJX-18-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-18-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path><path id="MJX-18-TEX-I-1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path><path id="MJX-18-TEX-N-2192" d="M56 237T56 250T70 270H835Q719 357 692 493Q692 494 692 496T691 499Q691 511 708 511H711Q720 511 723 510T729 506T732 497T735 481T743 456Q765 389 816 336T935 261Q944 258 944 250Q944 244 939 241T915 231T877 212Q836 186 806 152T761 85T740 35T732 4Q730 -6 727 -8T711 -11Q691 -11 691 0Q691 7 696 25Q728 151 835 230H70Q56 237 56 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-18-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(716.7,0)"><use data-c="22EF" xlink:href="#MJX-18-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(2055.3,0)"><use data-c="1D453" xlink:href="#MJX-18-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(2605.3,0)"><use data-c="1D454" xlink:href="#MJX-18-TEX-I-1D454"></use></g><g data-mml-node="mi" transform="translate(3082.3,0)"><use data-c="1D453" xlink:href="#MJX-18-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(3910.1,0)"><use data-c="2192" xlink:href="#MJX-18-TEX-N-2192"></use></g><g data-mml-node="mi" transform="translate(5187.9,0)"><use data-c="1D453" xlink:href="#MJX-18-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(5904.6,0)"><use data-c="22EF" xlink:href="#MJX-18-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(7243.2,0)"><use data-c="1D453" xlink:href="#MJX-18-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(7793.2,0)"><use data-c="1D454" xlink:href="#MJX-18-TEX-I-1D454"></use></g><g data-mml-node="mi" transform="translate(8270.2,0)"><use data-c="1D454" xlink:href="#MJX-18-TEX-I-1D454"></use></g></g></g></svg></mjx-container><script type="math/tex">f\cdots fgf \rightarrow f\cdots fgg</script></p> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:pink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:pink,stroke:#333,stroke-width:4px f --> fg((g)); g --> gf((f)); g --> gg((g)); ff --> fff((f)); ff --> ffg((g)); style ffg fill:pink,stroke:#333,stroke-width:4px fg --> fgf((f)); fg --> fgg((g)); gf --> gff((f)); gf --> gfg((g)); gg --> ggf((f)); gg --> ggg((g)); fff --> ffff((f)); fff --> fffg((g)); ffg --> ffgf((f)); ffg --> ffgg((g)); style ffgg fill:pink,stroke:#333,stroke-width:4px fgf --> fgff((f)); fgf --> fgfg((g)); fgg --> fggf((f)); fgg --> fggg((g)); gff --> gfff((f)); gff --> gffg((g)); gfg --> gfgf((f)); gfg --> gfgg((g)); ggf --> ggff((f)); ggf --> ggfg((g)); ggg --> gggf((f)); ggg --> gggg((g)); </code></pre> </blockquote> <p>对此，我们发现一个 <code>比较严重的问题</code>。</p> <p>我们观察到，该 <code>深度优先搜索</code>方法在 <code>每一个递归层次</code>都会 <code>按顺序执行</code><mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="4.299ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 1900 1000" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.566ex;"><defs><path id="MJX-19-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-19-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-19-TEX-I-1D465" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path id="MJX-19-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-19-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(550,0)"><use data-c="28" xlink:href="#MJX-19-TEX-N-28"></use></g><g data-mml-node="mi" transform="translate(939,0)"><use data-c="1D465" xlink:href="#MJX-19-TEX-I-1D465"></use></g><g data-mml-node="mo" transform="translate(1511,0)"><use data-c="29" xlink:href="#MJX-19-TEX-N-29"></use></g></g></g></svg></mjx-container><script type="math/tex">f(x)</script>和<mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="4.133ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 1827 1000" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.566ex;"><defs><path id="MJX-20-TEX-I-1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path><path id="MJX-20-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-20-TEX-I-1D465" d="M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z"></path><path id="MJX-20-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D454" xlink:href="#MJX-20-TEX-I-1D454"></use></g><g data-mml-node="mo" transform="translate(477,0)"><use data-c="28" xlink:href="#MJX-20-TEX-N-28"></use></g><g data-mml-node="mi" transform="translate(866,0)"><use data-c="1D465" xlink:href="#MJX-20-TEX-I-1D465"></use></g><g data-mml-node="mo" transform="translate(1438,0)"><use data-c="29" xlink:href="#MJX-20-TEX-N-29"></use></g></g></g></svg></mjx-container><script type="math/tex">g(x)</script>，</p> <p>所以，它会先 <code>沿着一条路径不断下降到</code> <mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="8.383ex" height="2.059ex" role="img" focusable="false" viewBox="0 -705 3705.3 910" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.464ex;"><defs><path id="MJX-21-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path><path id="MJX-21-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-21-TEX-I-1D453"></use></g><g data-mml-node="mo" transform="translate(716.7,0)"><use data-c="22EF" xlink:href="#MJX-21-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(2055.3,0)"><use data-c="1D453" xlink:href="#MJX-21-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(2605.3,0)"><use data-c="1D453" xlink:href="#MJX-21-TEX-I-1D453"></use></g><g data-mml-node="mi" transform="translate(3155.3,0)"><use data-c="1D453" xlink:href="#MJX-21-TEX-I-1D453"></use></g></g></g></svg></mjx-container><script type="math/tex">f \cdots fff</script></p> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:pink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:pink,stroke:#333,stroke-width:4px f --> fg((g)); g --> gf((f)); g --> gg((g)); ff --> fff((f)); style fff fill:pink,stroke:#333,stroke-width:4px ff --> ffg((g)); fg --> fgf((f)); fg --> fgg((g)); gf --> gff((f)); gf --> gfg((g)); gg --> ggf((f)); gg --> ggg((g)); fff --> ffff((f)); style ffff fill:pink,stroke:#333,stroke-width:4px fff --> fffg((g)); ffg --> ffgf((f)); ffg --> ffgg((g)); fgf --> fgff((f)); fgf --> fgfg((g)); fgg --> fggf((f)); fgg --> fggg((g)); gff --> gfff((f)); gff --> gffg((g)); gfg --> gfgf((f)); gfg --> gfgg((g)); ggf --> ggff((f)); ggf --> ggfg((g)); ggg --> gggf((f)); ggg --> gggg((g)); </code></pre> <p>如果，我们要寻找的 <code>最优解</code>它不是以<mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="1.244ex" height="2.059ex" role="img" focusable="false" viewBox="0 -705 550 910" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.464ex;"><defs><path id="MJX-22-TEX-I-1D453" d="M118 -162Q120 -162 124 -164T135 -167T147 -168Q160 -168 171 -155T187 -126Q197 -99 221 27T267 267T289 382V385H242Q195 385 192 387Q188 390 188 397L195 425Q197 430 203 430T250 431Q298 431 298 432Q298 434 307 482T319 540Q356 705 465 705Q502 703 526 683T550 630Q550 594 529 578T487 561Q443 561 443 603Q443 622 454 636T478 657L487 662Q471 668 457 668Q445 668 434 658T419 630Q412 601 403 552T387 469T380 433Q380 431 435 431Q480 431 487 430T498 424Q499 420 496 407T491 391Q489 386 482 386T428 385H372L349 263Q301 15 282 -47Q255 -132 212 -173Q175 -205 139 -205Q107 -205 81 -186T55 -132Q55 -95 76 -78T118 -61Q162 -61 162 -103Q162 -122 151 -136T127 -157L118 -162Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D453" xlink:href="#MJX-22-TEX-I-1D453"></use></g></g></g></svg></mjx-container><script type="math/tex">f</script> <code>作为前缀的</code>，</p> <p>那么，我们对 <code>这整条深度优先搜索路径所做的搜索</code>的工作 <code>都是浪费的</code>！</p> <p>更极端地，如果 <code>最优解</code>是 <mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="7.722ex" height="1.464ex" role="img" focusable="false" viewBox="0 -442 3413.3 647" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.464ex;"><defs><path id="MJX-23-TEX-I-1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path><path id="MJX-23-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D454" xlink:href="#MJX-23-TEX-I-1D454"></use></g><g data-mml-node="mo" transform="translate(643.7,0)"><use data-c="22EF" xlink:href="#MJX-23-TEX-N-22EF"></use></g><g data-mml-node="mi" transform="translate(1982.3,0)"><use data-c="1D454" xlink:href="#MJX-23-TEX-I-1D454"></use></g><g data-mml-node="mi" transform="translate(2459.3,0)"><use data-c="1D454" xlink:href="#MJX-23-TEX-I-1D454"></use></g><g data-mml-node="mi" transform="translate(2936.3,0)"><use data-c="1D454" xlink:href="#MJX-23-TEX-I-1D454"></use></g></g></g></svg></mjx-container><script type="math/tex">g \cdots ggg</script>，那么，我们 <code>所做的绝大部分搜索</code>都将是 <code>无用的</code></p> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); root((root)) --> g((g)); style g fill:lightgreen,stroke:#333,stroke-width:4px f --> ff((f)); f --> fg((g)); g --> gf((f)); g --> gg((g)); style gg fill:lightgreen,stroke:#333,stroke-width:4px ff --> fff((f)); ff --> ffg((g)); fg --> fgf((f)); fg --> fgg((g)); gf --> gff((f)); gf --> gfg((g)); gg --> ggf((f)); gg --> ggg((g)); style ggg fill:lightgreen,stroke:#333,stroke-width:4px fff --> ffff((f)); fff --> fffg((g)); ffg --> ffgf((f)); ffg --> ffgg((g)); fgf --> fgff((f)); fgf --> fgfg((g)); fgg --> fggf((f)); fgg --> fggg((g)); gff --> gfff((f)); gff --> gffg((g)); gfg --> gfgf((f)); gfg --> gfgg((g)); ggf --> ggff((f)); ggf --> ggfg((g)); ggg --> gggf((f)); ggg --> gggg((g)); style gggg fill:lightgreen,stroke:#333,stroke-width:4px </code></pre> <p>不妨再考虑一个 <code>不幸运的情况</code>：<code>最优解</code> 如果是 <code>以g作为前缀</code>，但 <code>它的长度却比较小</code>。</p> <p>那么我们也会做 <code>大部分没有意义的搜索</code>，因为该 <code>算法</code>不管 <code>最优解的长度有多么小</code>，都要按 <code>深度优先搜索</code>的方式，<code>不断下降（使转变函数序列的长度增长）</code>，不断 <code>下降</code>和 <code>回溯</code> 寻求解。(如果在 <code>下降过程</code>没有发现解，那么就只能通过 <code>回溯</code>后接着 <code>下降</code>，再继续寻找解)</p> <h4>Iterative-Deepening DFS</h4> <p>首先，我们解决一下 <code>这个不幸运的情况</code>：如果 <code>最优解</code>它足够短，我们希望 <code>搜索算法</code>不要 <code>下降到我们设定的最大深度</code>，然后通过 <code>逐步回溯</code>来发现这个 <code>长度较短的最优解</code>。而是说，我们希望让 <code>搜索算法</code>尽量找找看，有没有 <code>长度较短的解</code>，如果 <code>长度较短的解</code> <code>的确找不到</code>，那么我们再 <code>寻找长度较长的解</code></p> <blockquote><p>实际上，根据这道题目的性质。我们也不应该采用 <code>深度优先搜索</code>。</p> </blockquote> <p>因此，我们可以使用 <code>迭代加深搜索 (Iterative-Deepening DFS)</code>：</p> <ul> <li>在 <code>深度为1的解空间树</code>中进行 <code>搜索</code>，若找到 <code>解</code>则立即返回。</li> <li>在 <code>深度为2的解空间树</code>中进行 <code>搜索</code>，若找到 <code>解</code>则立即返回。</li> <li><mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="2.652ex" height="0.271ex" role="img" focusable="false" viewBox="0 -310 1172 120" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: 0.43ex;"><defs><path id="MJX-38-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mo"><use data-c="22EF" xlink:href="#MJX-38-TEX-N-22EF"></use></g></g></g></svg></mjx-container><script type="math/tex">\cdots</script></li> <li>在 <code>深度为k的解空间树</code> 中进行 <code>搜索</code>，若找到 <code>解</code>则立即返回。</li> <li>在 <code>深度为k以内的解空间树</code>中 <code>无解</code>！</li> </ul> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:lightpink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:lightgray,stroke:#333,stroke-width:4px f --> fg((g)); style fg fill:lightgray,stroke:#333,stroke-width:4px g --> gf((f)); style gf fill:lightgray,stroke:#333,stroke-width:4px g --> gg((g)); style gg fill:lightgray,stroke:#333,stroke-width:4px ff --> fff((f)); style fff fill:lightgray,stroke:#333,stroke-width:4px ff --> ffg((g)); style ffg fill:lightgray,stroke:#333,stroke-width:4px fg --> fgf((f)); style fgf fill:lightgray,stroke:#333,stroke-width:4px fg --> fgg((g)); style fgg fill:lightgray,stroke:#333,stroke-width:4px gf --> gff((f)); style gff fill:lightgray,stroke:#333,stroke-width:4px gf --> gfg((g)); style gfg fill:lightgray,stroke:#333,stroke-width:4px gg --> ggf((f)); style ggf fill:lightgray,stroke:#333,stroke-width:4px gg --> ggg((g)); style ggg fill:lightgray,stroke:#333,stroke-width:4px fff --> ffff((f)); style ffff fill:lightgray,stroke:#333,stroke-width:4px fff --> fffg((g)); style fffg fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgf((f)); style ffgf fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgg((g)); style ffgg fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgff((f)); style fgff fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgfg((g)); style fgfg fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggf((f)); style fggf fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggg((g)); style fggg fill:lightgray,stroke:#333,stroke-width:4px gff --> gfff((f)); style gfff fill:lightgray,stroke:#333,stroke-width:4px gff --> gffg((g)); style gffg fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgf((f)); style gfgf fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgg((g)); style gfgg fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggff((f)); style ggff fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggfg((g)); style ggfg fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggf((f)); style gggf fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggg((g)); style gggg fill:lightgray,stroke:#333,stroke-width:4px </code></pre> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); root((root)) --> g((g)); style g fill:lightpink,stroke:#333,stroke-width:4px f --> ff((f)); style ff fill:lightgray,stroke:#333,stroke-width:4px f --> fg((g)); style fg fill:lightgray,stroke:#333,stroke-width:4px g --> gf((f)); style gf fill:lightgray,stroke:#333,stroke-width:4px g --> gg((g)); style gg fill:lightgray,stroke:#333,stroke-width:4px ff --> fff((f)); style fff fill:lightgray,stroke:#333,stroke-width:4px ff --> ffg((g)); style ffg fill:lightgray,stroke:#333,stroke-width:4px fg --> fgf((f)); style fgf fill:lightgray,stroke:#333,stroke-width:4px fg --> fgg((g)); style fgg fill:lightgray,stroke:#333,stroke-width:4px gf --> gff((f)); style gff fill:lightgray,stroke:#333,stroke-width:4px gf --> gfg((g)); style gfg fill:lightgray,stroke:#333,stroke-width:4px gg --> ggf((f)); style ggf fill:lightgray,stroke:#333,stroke-width:4px gg --> ggg((g)); style ggg fill:lightgray,stroke:#333,stroke-width:4px fff --> ffff((f)); style ffff fill:lightgray,stroke:#333,stroke-width:4px fff --> fffg((g)); style fffg fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgf((f)); style ffgf fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgg((g)); style ffgg fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgff((f)); style fgff fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgfg((g)); style fgfg fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggf((f)); style fggf fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggg((g)); style fggg fill:lightgray,stroke:#333,stroke-width:4px gff --> gfff((f)); style gfff fill:lightgray,stroke:#333,stroke-width:4px gff --> gffg((g)); style gffg fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgf((f)); style gfgf fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgg((g)); style gfgg fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggff((f)); style ggff fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggfg((g)); style ggfg fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggf((f)); style gggf fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggg((g)); style gggg fill:lightgray,stroke:#333,stroke-width:4px </code></pre> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:lightpink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); style ff fill:lightpink,stroke:#333,stroke-width:4px f --> fg((g)); g --> gf((f)); g --> gg((g)); ff --> fff((f)); style fff fill:lightgray,stroke:#333,stroke-width:4px ff --> ffg((g)); style ffg fill:lightgray,stroke:#333,stroke-width:4px fg --> fgf((f)); style fgf fill:lightgray,stroke:#333,stroke-width:4px fg --> fgg((g)); style fgg fill:lightgray,stroke:#333,stroke-width:4px gf --> gff((f)); style gff fill:lightgray,stroke:#333,stroke-width:4px gf --> gfg((g)); style gfg fill:lightgray,stroke:#333,stroke-width:4px gg --> ggf((f)); style ggf fill:lightgray,stroke:#333,stroke-width:4px gg --> ggg((g)); style ggg fill:lightgray,stroke:#333,stroke-width:4px fff --> ffff((f)); style ffff fill:lightgray,stroke:#333,stroke-width:4px fff --> fffg((g)); style fffg fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgf((f)); style ffgf fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgg((g)); style ffgg fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgff((f)); style fgff fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgfg((g)); style fgfg fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggf((f)); style fggf fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggg((g)); style fggg fill:lightgray,stroke:#333,stroke-width:4px gff --> gfff((f)); style gfff fill:lightgray,stroke:#333,stroke-width:4px gff --> gffg((g)); style gffg fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgf((f)); style gfgf fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgg((g)); style gfgg fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggff((f)); style ggff fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggfg((g)); style ggfg fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggf((f)); style gggf fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggg((g)); style gggg fill:lightgray,stroke:#333,stroke-width:4px </code></pre> <pre><code class="language-mermaid" lang="mermaid">graph TD; root((root)) --> f((f)); style f fill:lightpink,stroke:#333,stroke-width:4px root((root)) --> g((g)); f --> ff((f)); f --> fg((g)); style fg fill:lightpink,stroke:#333,stroke-width:4px g --> gf((f)); g --> gg((g)); ff --> fff((f)); style fff fill:lightgray,stroke:#333,stroke-width:4px ff --> ffg((g)); style ffg fill:lightgray,stroke:#333,stroke-width:4px fg --> fgf((f)); style fgf fill:lightgray,stroke:#333,stroke-width:4px fg --> fgg((g)); style fgg fill:lightgray,stroke:#333,stroke-width:4px gf --> gff((f)); style gff fill:lightgray,stroke:#333,stroke-width:4px gf --> gfg((g)); style gfg fill:lightgray,stroke:#333,stroke-width:4px gg --> ggf((f)); style ggf fill:lightgray,stroke:#333,stroke-width:4px gg --> ggg((g)); style ggg fill:lightgray,stroke:#333,stroke-width:4px fff --> ffff((f)); style ffff fill:lightgray,stroke:#333,stroke-width:4px fff --> fffg((g)); style fffg fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgf((f)); style ffgf fill:lightgray,stroke:#333,stroke-width:4px ffg --> ffgg((g)); style ffgg fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgff((f)); style fgff fill:lightgray,stroke:#333,stroke-width:4px fgf --> fgfg((g)); style fgfg fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggf((f)); style fggf fill:lightgray,stroke:#333,stroke-width:4px fgg --> fggg((g)); style fggg fill:lightgray,stroke:#333,stroke-width:4px gff --> gfff((f)); style gfff fill:lightgray,stroke:#333,stroke-width:4px gff --> gffg((g)); style gffg fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgf((f)); style gfgf fill:lightgray,stroke:#333,stroke-width:4px gfg --> gfgg((g)); style gfgg fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggff((f)); style ggff fill:lightgray,stroke:#333,stroke-width:4px ggf --> ggfg((g)); style ggfg fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggf((f)); style gggf fill:lightgray,stroke:#333,stroke-width:4px ggg --> gggg((g)); style gggg fill:lightgray,stroke:#333,stroke-width:4px </code></pre> <p><mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="2.652ex" height="0.271ex" role="img" focusable="false" viewBox="0 -310 1172 120" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: 0.43ex;"><defs><path id="MJX-38-TEX-N-22EF" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250ZM525 250Q525 274 542 292T585 310Q609 310 627 294T646 251Q646 226 629 208T586 190T543 207T525 250ZM972 250Q972 274 989 292T1032 310Q1056 310 1074 294T1093 251Q1093 226 1076 208T1033 190T990 207T972 250Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mo"><use data-c="22EF" xlink:href="#MJX-38-TEX-N-22EF"></use></g></g></g></svg></mjx-container><script type="math/tex">\cdots</script></p> <blockquote><p>注意两点：</p> <ul> <li><p>我们可以 <code>立即返回</code>是因为：根据 <code>题目性质</code>，要求求解 <code>最短/最小的解</code></p> </li> <li><p>算法最终 <code>报告无解</code>并不一定表示 <code>原问题无解</code>：这取决于 <code>我们设定的最大递归深度</code><mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="1.179ex" height="1.595ex" role="img" focusable="false" viewBox="0 -694 521 705" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.025ex;"><defs><path id="MJX-26-TEX-I-1D458" d="M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D458" xlink:href="#MJX-26-TEX-I-1D458"></use></g></g></g></svg></mjx-container><script type="math/tex">k</script> </p> <blockquote><p>最大深度<mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="1.179ex" height="1.595ex" role="img" focusable="false" viewBox="0 -694 521 705" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.025ex;"><defs><path id="MJX-26-TEX-I-1D458" d="M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><use data-c="1D458" xlink:href="#MJX-26-TEX-I-1D458"></use></g></g></g></svg></mjx-container><script type="math/tex">k</script>的设定需要我们根据题目分析得到，它可以是 <code>静态的</code>，也可以是 <code>动态的</code>。</p> <p>它可以是 <code>不确切的上界</code>，但至少我们希望 <code>要保证k足够大，使得不会遗漏解</code></p> </blockquote> </li> </ul> </blockquote> <p>于是，我们需要做下面这些工作：</p> <ul> <li><p>定义 <code>递归次数的上界估计函数 (价值函数)</code><mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="28.436ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 12568.8 1000" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.566ex;"><defs><path id="MJX-27-TEX-N-27F9" d="M1218 514Q1218 525 1234 525Q1239 525 1242 525T1247 525T1251 524T1253 523T1255 520T1257 517T1260 512Q1297 438 1358 381T1469 300T1565 263Q1582 258 1582 250T1573 239T1536 228T1478 204Q1334 134 1260 -12Q1256 -21 1253 -22T1238 -24Q1218 -24 1218 -17Q1218 -13 1223 0Q1258 69 1309 123L1319 133H70Q56 140 56 153Q56 168 72 173H1363L1373 181Q1412 211 1490 250Q1489 251 1472 259T1427 283T1373 319L1363 327H710L707 328L390 327H72Q56 332 56 347Q56 360 70 367H1319L1309 377Q1276 412 1247 458T1218 514Z"></path><path id="MJX-27-TEX-N-65" d="M28 218Q28 273 48 318T98 391T163 433T229 448Q282 448 320 430T378 380T406 316T415 245Q415 238 408 231H126V216Q126 68 226 36Q246 30 270 30Q312 30 342 62Q359 79 369 104L379 128Q382 131 395 131H398Q415 131 415 121Q415 117 412 108Q393 53 349 21T250 -11Q155 -11 92 58T28 218ZM333 275Q322 403 238 411H236Q228 411 220 410T195 402T166 381T143 340T127 274V267H333V275Z"></path><path id="MJX-27-TEX-N-73" d="M295 316Q295 356 268 385T190 414Q154 414 128 401Q98 382 98 349Q97 344 98 336T114 312T157 287Q175 282 201 278T245 269T277 256Q294 248 310 236T342 195T359 133Q359 71 321 31T198 -10H190Q138 -10 94 26L86 19L77 10Q71 4 65 -1L54 -11H46H42Q39 -11 33 -5V74V132Q33 153 35 157T45 162H54Q66 162 70 158T75 146T82 119T101 77Q136 26 198 26Q295 26 295 104Q295 133 277 151Q257 175 194 187T111 210Q75 227 54 256T33 318Q33 357 50 384T93 424T143 442T187 447H198Q238 447 268 432L283 424L292 431Q302 440 314 448H322H326Q329 448 335 442V310L329 304H301Q295 310 295 316Z"></path><path id="MJX-27-TEX-N-74" d="M27 422Q80 426 109 478T141 600V615H181V431H316V385H181V241Q182 116 182 100T189 68Q203 29 238 29Q282 29 292 100Q293 108 293 146V181H333V146V134Q333 57 291 17Q264 -10 221 -10Q187 -10 162 2T124 33T105 68T98 100Q97 107 97 248V385H18V422H27Z"></path><path id="MJX-27-TEX-N-69" d="M69 609Q69 637 87 653T131 669Q154 667 171 652T188 609Q188 579 171 564T129 549Q104 549 87 564T69 609ZM247 0Q232 3 143 3Q132 3 106 3T56 1L34 0H26V46H42Q70 46 91 49Q100 53 102 60T104 102V205V293Q104 345 102 359T88 378Q74 385 41 385H30V408Q30 431 32 431L42 432Q52 433 70 434T106 436Q123 437 142 438T171 441T182 442H185V62Q190 52 197 50T232 46H255V0H247Z"></path><path id="MJX-27-TEX-N-6D" d="M41 46H55Q94 46 102 60V68Q102 77 102 91T102 122T103 161T103 203Q103 234 103 269T102 328V351Q99 370 88 376T43 385H25V408Q25 431 27 431L37 432Q47 433 65 434T102 436Q119 437 138 438T167 441T178 442H181V402Q181 364 182 364T187 369T199 384T218 402T247 421T285 437Q305 442 336 442Q351 442 364 440T387 434T406 426T421 417T432 406T441 395T448 384T452 374T455 366L457 361L460 365Q463 369 466 373T475 384T488 397T503 410T523 422T546 432T572 439T603 442Q729 442 740 329Q741 322 741 190V104Q741 66 743 59T754 49Q775 46 803 46H819V0H811L788 1Q764 2 737 2T699 3Q596 3 587 0H579V46H595Q656 46 656 62Q657 64 657 200Q656 335 655 343Q649 371 635 385T611 402T585 404Q540 404 506 370Q479 343 472 315T464 232V168V108Q464 78 465 68T468 55T477 49Q498 46 526 46H542V0H534L510 1Q487 2 460 2T422 3Q319 3 310 0H302V46H318Q379 46 379 62Q380 64 380 200Q379 335 378 343Q372 371 358 385T334 402T308 404Q263 404 229 370Q202 343 195 315T187 232V168V108Q187 78 188 68T191 55T200 49Q221 46 249 46H265V0H257L234 1Q210 2 183 2T145 3Q42 3 33 0H25V46H41Z"></path><path id="MJX-27-TEX-N-61" d="M137 305T115 305T78 320T63 359Q63 394 97 421T218 448Q291 448 336 416T396 340Q401 326 401 309T402 194V124Q402 76 407 58T428 40Q443 40 448 56T453 109V145H493V106Q492 66 490 59Q481 29 455 12T400 -6T353 12T329 54V58L327 55Q325 52 322 49T314 40T302 29T287 17T269 6T247 -2T221 -8T190 -11Q130 -11 82 20T34 107Q34 128 41 147T68 188T116 225T194 253T304 268H318V290Q318 324 312 340Q290 411 215 411Q197 411 181 410T156 406T148 403Q170 388 170 359Q170 334 154 320ZM126 106Q126 75 150 51T209 26Q247 26 276 49T315 109Q317 116 318 175Q318 233 317 233Q309 233 296 232T251 223T193 203T147 166T126 106Z"></path><path id="MJX-27-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-27-TEX-N-72" d="M36 46H50Q89 46 97 60V68Q97 77 97 91T98 122T98 161T98 203Q98 234 98 269T98 328L97 351Q94 370 83 376T38 385H20V408Q20 431 22 431L32 432Q42 433 60 434T96 436Q112 437 131 438T160 441T171 442H174V373Q213 441 271 441H277Q322 441 343 419T364 373Q364 352 351 337T313 322Q288 322 276 338T263 372Q263 381 265 388T270 400T273 405Q271 407 250 401Q234 393 226 386Q179 341 179 207V154Q179 141 179 127T179 101T180 81T180 66V61Q181 59 183 57T188 54T193 51T200 49T207 48T216 47T225 47T235 46T245 46H276V0H267Q249 3 140 3Q37 3 28 0H20V46H36Z"></path><path id="MJX-27-TEX-N-67" d="M329 409Q373 453 429 453Q459 453 472 434T485 396Q485 382 476 371T449 360Q416 360 412 390Q410 404 415 411Q415 412 416 414V415Q388 412 363 393Q355 388 355 386Q355 385 359 381T368 369T379 351T388 325T392 292Q392 230 343 187T222 143Q172 143 123 171Q112 153 112 133Q112 98 138 81Q147 75 155 75T227 73Q311 72 335 67Q396 58 431 26Q470 -13 470 -72Q470 -139 392 -175Q332 -206 250 -206Q167 -206 107 -175Q29 -140 29 -75Q29 -39 50 -15T92 18L103 24Q67 55 67 108Q67 155 96 193Q52 237 52 292Q52 355 102 398T223 442Q274 442 318 416L329 409ZM299 343Q294 371 273 387T221 404Q192 404 171 388T145 343Q142 326 142 292Q142 248 149 227T179 192Q196 182 222 182Q244 182 260 189T283 207T294 227T299 242Q302 258 302 292T299 343ZM403 -75Q403 -50 389 -34T348 -11T299 -2T245 0H218Q151 0 138 -6Q118 -15 107 -34T95 -74Q95 -84 101 -97T122 -127T170 -155T250 -167Q319 -167 361 -139T403 -75Z"></path><path id="MJX-27-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path id="MJX-27-TEX-N-20" d=""></path><path id="MJX-27-TEX-N-2D" d="M11 179V252H277V179H11Z"></path><path id="MJX-27-TEX-N-3E" d="M84 520Q84 528 88 533T96 539L99 540Q106 540 253 471T544 334L687 265Q694 260 694 250T687 235Q685 233 395 96L107 -40H101Q83 -38 83 -20Q83 -19 83 -17Q82 -10 98 -1Q117 9 248 71Q326 108 378 132L626 250L378 368Q90 504 86 509Q84 513 84 520Z"></path><path id="MJX-27-TEX-N-6E" d="M41 46H55Q94 46 102 60V68Q102 77 102 91T102 122T103 161T103 203Q103 234 103 269T102 328V351Q99 370 88 376T43 385H25V408Q25 431 27 431L37 432Q47 433 65 434T102 436Q119 437 138 438T167 441T178 442H181V402Q181 364 182 364T187 369T199 384T218 402T247 421T285 437Q305 442 336 442Q450 438 463 329Q464 322 464 190V104Q464 66 466 59T477 49Q498 46 526 46H542V0H534L510 1Q487 2 460 2T422 3Q319 3 310 0H302V46H318Q379 46 379 62Q380 64 380 200Q379 335 378 343Q372 371 358 385T334 402T308 404Q263 404 229 370Q202 343 195 315T187 232V168V108Q187 78 188 68T191 55T200 49Q221 46 249 46H265V0H257L234 1Q210 2 183 2T145 3Q42 3 33 0H25V46H41Z"></path><path id="MJX-27-TEX-N-6B" d="M36 46H50Q89 46 97 60V68Q97 77 97 91T97 124T98 167T98 217T98 272T98 329Q98 366 98 407T98 482T98 542T97 586T97 603Q94 622 83 628T38 637H20V660Q20 683 22 683L32 684Q42 685 61 686T98 688Q115 689 135 690T165 693T176 694H179V463L180 233L240 287Q300 341 304 347Q310 356 310 364Q310 383 289 385H284V431H293Q308 428 412 428Q475 428 484 431H489V385H476Q407 380 360 341Q286 278 286 274Q286 273 349 181T420 79Q434 60 451 53T500 46H511V0H505Q496 3 418 3Q322 3 307 0H299V46H306Q330 48 330 65Q330 72 326 79Q323 84 276 153T228 222L176 176V120V84Q176 65 178 59T189 49Q210 46 238 46H254V0H246Q231 3 137 3T28 0H20V46H36Z"></path><path id="MJX-27-TEX-N-A0" d=""></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mstyle"><g data-mml-node="mspace"></g></g><g data-mml-node="mo" transform="translate(278,0)"><use data-c="27F9" xlink:href="#MJX-27-TEX-N-27F9"></use></g><g data-mml-node="mstyle" transform="translate(1916,0)"><g data-mml-node="mspace"></g></g><g data-mml-node="mtext" transform="translate(2471.8,0)"><use data-c="65" xlink:href="#MJX-27-TEX-N-65"></use><use data-c="73" xlink:href="#MJX-27-TEX-N-73" transform="translate(444,0)"></use><use data-c="74" xlink:href="#MJX-27-TEX-N-74" transform="translate(838,0)"></use><use data-c="69" xlink:href="#MJX-27-TEX-N-69" transform="translate(1227,0)"></use><use data-c="6D" xlink:href="#MJX-27-TEX-N-6D" transform="translate(1505,0)"></use><use data-c="61" xlink:href="#MJX-27-TEX-N-61" transform="translate(2338,0)"></use><use data-c="74" xlink:href="#MJX-27-TEX-N-74" transform="translate(2838,0)"></use><use data-c="65" xlink:href="#MJX-27-TEX-N-65" transform="translate(3227,0)"></use><use data-c="28" xlink:href="#MJX-27-TEX-N-28" transform="translate(3671,0)"></use><use data-c="61" xlink:href="#MJX-27-TEX-N-61" transform="translate(4060,0)"></use><use data-c="72" xlink:href="#MJX-27-TEX-N-72" transform="translate(4560,0)"></use><use data-c="67" xlink:href="#MJX-27-TEX-N-67" transform="translate(4952,0)"></use><use data-c="73" xlink:href="#MJX-27-TEX-N-73" transform="translate(5452,0)"></use><use data-c="29" xlink:href="#MJX-27-TEX-N-29" transform="translate(5846,0)"></use><use data-c="20" xlink:href="#MJX-27-TEX-N-20" transform="translate(6235,0)"></use><use data-c="2D" xlink:href="#MJX-27-TEX-N-2D" transform="translate(6485,0)"></use><use data-c="3E" xlink:href="#MJX-27-TEX-N-3E" transform="translate(6818,0)"></use><use data-c="20" xlink:href="#MJX-27-TEX-N-20" transform="translate(7596,0)"></use><use data-c="69" xlink:href="#MJX-27-TEX-N-69" transform="translate(7846,0)"></use><use data-c="6E" xlink:href="#MJX-27-TEX-N-6E" transform="translate(8124,0)"></use><use data-c="74" xlink:href="#MJX-27-TEX-N-74" transform="translate(8680,0)"></use><use data-c="20" xlink:href="#MJX-27-TEX-N-20" transform="translate(9069,0)"></use><use data-c="6B" xlink:href="#MJX-27-TEX-N-6B" transform="translate(9319,0)"></use><use data-c="A0" xlink:href="#MJX-27-TEX-N-A0" transform="translate(9847,0)"></use></g></g></g></svg></mjx-container><script type="math/tex">\implies \text{estimate(args) -> int k } </script></p> <blockquote><p>在 <code>DFS Method</code>中，我们并没有定义这个 <code>上界估计函数</code>，</p> <p>因为<del>我们偷偷看了输入数据</del> 如果 <code>k的上界</code>非常大的话，对于 <code>DFS Method</code>方法是 <code>没有意义的</code>，</p> <p>因为根据 <code>DFS</code>和 <code>该问题的特性</code>，<code>所产生的DFS树</code>会 <code>迅速膨胀</code>到 <code>我们无法在规定时间内求得解</code>，而这个 <code>非常大的k值</code>也 <code>根本不会被触碰到</code></p> </blockquote> <blockquote><p>对于 <code>IDDFS</code>，我们可以根据 <code>题目性质</code> 设置 <code>合适的上界估计函数</code>。</p> <blockquote><p>但要注意，如果 <code>最优解</code>的 <code>深度</code>确实很大，那么 <code>IDDFS</code>也会面临 <code>DFS树</code> <code>迅速膨胀</code> 的 <code>困境</code></p> <blockquote><p>不过，<code>IDDFS</code>对于 <code>最优解的深度较小的情况</code>是非常适合的。</p> </blockquote> </blockquote> </blockquote> </li> <li><p>根据 <code>题目性质</code>为 <code>递归方法</code> 定义 <code>所需的全局变量</code></p> <blockquote><p>我们当然可以使用 <code>递归方法所属的方法栈的局部内存</code>来存储 <code>所需要的变量</code></p> <ul> <li>但是，这往往会导致 <code>重复拷贝和传递相同的参数</code>和 <code>产生大量结构高度相似的冗余信息</code></li> </ul> <p>这不仅仅是 <code>空间</code>上的问题，还包括做这些工作所用的 <code>时间</code></p> <blockquote><p>如果你使用的是 <code>C/C++</code>等提供 <code>指针/引用</code>的 <code>编程语言</code>，可能会有些 <code>奇怪的想法</code>。</p> <p>但请重新考虑一下：<code>一个4字节的指针</code>并不会比 <code>一个4字节的整数</code>更节约空间。</p> </blockquote> <blockquote><p>一般来说，<code>每个递归方法的一个帧栈</code>如果 <code>只做一个选择</code>，那么我们实际上只需要 <code>保存所做的选择</code>和 <code>当前深度</code>即可。</p> <blockquote><p>比如说，要求 <code>每一个递归方法的函数调用帧栈</code> 进行 <code>选择一个数字</code>，<code>选择一个转变函数</code>等等。</p> </blockquote> </blockquote> <ul> <li>使用 <code>递归函数的函数调用帧栈</code>但 <code>仅保存必要信息</code></li> </ul> <p>该方法可行，但 <code>回溯</code>时会稍微麻烦一些，仍然不如直接使用 <code>全局变量</code></p> </blockquote> </li> <li><p>按k递增方式执行k次 <code>DFS</code> <mjx-container class="MathJax" jax="SVG" style="position: relative;"><svg xmlns="http://www.w3.org/2000/svg" width="28.68ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 12676.8 1000" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true" style="vertical-align: -0.566ex;"><defs><path id="MJX-28-TEX-N-27F9" d="M1218 514Q1218 525 1234 525Q1239 525 1242 525T1247 525T1251 524T1253 523T1255 520T1257 517T1260 512Q1297 438 1358 381T1469 300T1565 263Q1582 258 1582 250T1573 239T1536 228T1478 204Q1334 134 1260 -12Q1256 -21 1253 -22T1238 -24Q1218 -24 1218 -17Q1218 -13 1223 0Q1258 69 1309 123L1319 133H70Q56 140 56 153Q56 168 72 173H1363L1373 181Q1412 211 1490 250Q1489 251 1472 259T1427 283T1373 319L1363 327H710L707 328L390 327H72Q56 332 56 347Q56 360 70 367H1319L1309 377Q1276 412 1247 458T1218 514Z"></path><path id="MJX-28-TEX-N-73" d="M295 316Q295 356 268 385T190 414Q154 414 128 401Q98 382 98 349Q97 344 98 336T114 312T157 287Q175 282 201 278T245 269T277 256Q294 248 310 236T342 195T359 133Q359 71 321 31T198 -10H190Q138 -10 94 26L86 19L77 10Q71 4 65 -1L54 -11H46H42Q39 -11 33 -5V74V132Q33 153 35 157T45 162H54Q66 162 70 158T75 146T82 119T101 77Q136 26 198 26Q295 26 295 104Q295 133 277 151Q257 175 194 187T111 210Q75 227 54 256T33 318Q33 357 50 384T93 424T143 442T187 447H198Q238 447 268 432L283 424L292 431Q302 440 314 448H322H326Q329 448 335 442V310L329 304H301Q295 310 295 316Z"></path><path id="MJX-28-TEX-N-65" d="M28 218Q28 273 48 318T98 391T163 433T229 448Q282 448 320 430T378 380T406 316T415 245Q415 238 408 231H126V216Q126 68 226 36Q246 30 270 30Q312 30 342 62Q359 79 369 104L379 128Q382 131 395 131H398Q415 131 415 121Q415 117 412 108Q393 53 349 21T250 -11Q155 -11 92 58T28 218ZM333 275Q322 403 238 411H236Q228 411 220 410T195 402T166 381T143 340T127 274V267H333V275Z"></path><path id="MJX-28-TEX-N-61" d="M137 305T115 305T78 320T63 359Q63 394 97 421T218 448Q291 448 336 416T396 340Q401 326 401 309T402 194V124Q402 76 407 58T428 40Q443 40 448 56T453 109V145H493V106Q492 66 490 59Q481 29 455 12T400 -6T353 12T329 54V58L327 55Q325 52 322 49T314 40T302 29T287 17T269 6T247 -2T221 -8T190 -11Q130 -11 82 20T34 107Q34 128 41 147T68 188T116 225T194 253T304 268H318V290Q318 324 312 340Q290 411 215 411Q197 411 181 410T156 406T148 403Q170 388 170 359Q170 334 154 320ZM126 106Q126 75 150 51T209 26Q247 26 276 49T315 109Q317 116 318 175Q318 233 317 233Q309 233 296 232T251 223T193 203T147 166T126 106Z"></path><path id="MJX-28-TEX-N-72" d="M36 46H50Q89 46 97 60V68Q97 77 97 91T98 122T98 161T98 203Q98 234 98 269T98 328L97 351Q94 370 83 376T38 385H20V408Q20 431 22 431L32 432Q42 433 60 434T96 436Q112 437 131 438T160 441T171 442H174V373Q213 441 271 441H277Q322 441 343 419T364 373Q364 352 351 337T313 322Q288 322 276 338T263 372Q263 381 265 388T270 400T273 405Q271 407 250 401Q234 393 226 386Q179 341 179 207V154Q179 141 179 127T179 101T180 81T180 66V61Q181 59 183 57T188 54T193 51T200 49T207 48T216 47T225 47T235 46T245 46H276V0H267Q249 3 140 3Q37 3 28 0H20V46H36Z"></path><path id="MJX-28-TEX-N-63" d="M370 305T349 305T313 320T297 358Q297 381 312 396Q317 401 317 402T307 404Q281 408 258 408Q209 408 178 376Q131 329 131 219Q131 137 162 90Q203 29 272 29Q313 29 338 55T374 117Q376 125 379 127T395 129H409Q415 123 415 120Q415 116 411 104T395 71T366 33T318 2T249 -11Q163 -11 99 53T34 214Q34 318 99 383T250 448T370 421T404 357Q404 334 387 320Z"></path><path id="MJX-28-TEX-N-68" d="M41 46H55Q94 46 102 60V68Q102 77 102 91T102 124T102 167T103 217T103 272T103 329Q103 366 103 407T103 482T102 542T102 586T102 603Q99 622 88 628T43 637H25V660Q25 683 27 683L37 684Q47 685 66 686T103 688Q120 689 140 690T170 693T181 694H184V367Q244 442 328 442Q451 442 463 329Q464 322 464 190V104Q464 66 466 59T477 49Q498 46 526 46H542V0H534L510 1Q487 2 460 2T422 3Q319 3 310 0H302V46H318Q379 46 379 62Q380 64 380 200Q379 335 378 343Q372 371 358 385T334 402T308 404Q263 404 229 370Q202 343 195 315T187 232V168V108Q187 78 188 68T191 55T200 49Q221 46 249 46H265V0H257L234 1Q210 2 183 2T145 3Q42 3 33 0H25V46H41Z"></path><path id="MJX-28-TEX-N-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path id="MJX-28-TEX-N-6B" d="M36 46H50Q89 46 97 60V68Q97 77 97 91T97 124T98 167T98 217T98 272T98 329Q98 366 98 407T98 482T98 542T97 586T97 603Q94 622 83 628T38 637H20V660Q20 683 22 683L32 684Q42 685 61 686T98 688Q115 689 135 690T165 693T176 694H179V463L180 233L240 287Q300 341 304 347Q310 356 310 364Q310 383 289 385H284V431H293Q308 428 412 428Q475 428 484 431H489V385H476Q407 380 360 341Q286 278 286 274Q286 273 349 181T420 79Q434 60 451 53T500 46H511V0H505Q496 3 418 3Q322 3 307 0H299V46H306Q330 48 330 65Q330 72 326 79Q323 84 276 153T228 222L176 176V120V84Q176 65 178 59T189 49Q210 46 238 46H254V0H246Q231 3 137 3T28 0H20V46H36Z"></path><path id="MJX-28-TEX-N-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path id="MJX-28-TEX-N-20" d=""></path><path id="MJX-28-TEX-N-2D" d="M11 179V252H277V179H11Z"></path><path id="MJX-28-TEX-N-3E" d="M84 520Q84 528 88 533T96 539L99 540Q106 540 253 471T544 334L687 265Q694 260 694 250T687 235Q685 233 395 96L107 -40H101Q83 -38 83 -20Q83 -19 83 -17Q82 -10 98 -1Q117 9 248 71Q326 108 378 132L626 250L378 368Q90 504 86 509Q84 513 84 520Z"></path><path id="MJX-28-TEX-N-62" d="M307 -11Q234 -11 168 55L158 37Q156 34 153 28T147 17T143 10L138 1L118 0H98V298Q98 599 97 603Q94 622 83 628T38 637H20V660Q20 683 22 683L32 684Q42 685 61 686T98 688Q115 689 135 690T165 693T176 694H179V543Q179 391 180 391L183 394Q186 397 192 401T207 411T228 421T254 431T286 439T323 442Q401 442 461 379T522 216Q522 115 458 52T307 -11ZM182 98Q182 97 187 90T196 79T206 67T218 55T233 44T250 35T271 29T295 26Q330 26 363 46T412 113Q424 148 424 212Q424 287 412 323Q385 405 300 405Q270 405 239 390T188 347L182 339V98Z"></path><path id="MJX-28-TEX-N-6F" d="M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z"></path><path id="MJX-28-TEX-N-6C" d="M42 46H56Q95 46 103 60V68Q103 77 103 91T103 124T104 167T104 217T104 272T104 329Q104 366 104 407T104 482T104 542T103 586T103 603Q100 622 89 628T44 637H26V660Q26 683 28 683L38 684Q48 685 67 686T104 688Q121 689 141 690T171 693T182 694H185V379Q185 62 186 60Q190 52 198 49Q219 46 247 46H263V0H255L232 1Q209 2 183 2T145 3T107 3T57 1L34 0H26V46H42Z"></path><path id="MJX-28-TEX-N-66" d="M273 0Q255 3 146 3Q43 3 34 0H26V46H42Q70 46 91 49Q99 52 103 60Q104 62 104 224V385H33V431H104V497L105 564L107 574Q126 639 171 668T266 704Q267 704 275 704T289 705Q330 702 351 679T372 627Q372 604 358 590T321 576T284 590T270 627Q270 647 288 667H284Q280 668 273 668Q245 668 223 647T189 592Q183 572 182 497V431H293V385H185V225Q185 63 186 61T189 57T194 54T199 51T206 49T213 48T222 47T231 47T241 46T251 46H282V0H273Z"></path><path id="MJX-28-TEX-N-75" d="M383 58Q327 -10 256 -10H249Q124 -10 105 89Q104 96 103 226Q102 335 102 348T96 369Q86 385 36 385H25V408Q25 431 27 431L38 432Q48 433 67 434T105 436Q122 437 142 438T172 441T184 442H187V261Q188 77 190 64Q193 49 204 40Q224 26 264 26Q290 26 311 35T343 58T363 90T375 120T379 144Q379 145 379 161T380 201T380 248V315Q380 361 370 372T320 385H302V431Q304 431 378 436T457 442H464V264Q464 84 465 81Q468 61 479 55T524 46H542V0Q540 0 467 -5T390 -11H383V58Z"></path><path id="MJX-28-TEX-N-6E" d="M41 46H55Q94 46 102 60V68Q102 77 102 91T102 122T103 161T103 203Q103 234 103 269T102 328V351Q99 370 88 376T43 385H25V408Q25 431 27 431L37 432Q47 433 65 434T102 436Q119 437 138 438T167 441T178 442H181V402Q181 364 182 364T187 369T199 384T218 402T247 421T285 437Q305 442 336 442Q450 438 463 329Q464 322 464 190V104Q464 66 466 59T477 49Q498 46 526 46H542V0H534L510 1Q487 2 460 2T422 3Q319 3 310 0H302V46H318Q379 46 379 62Q380 64 380 200Q379 335 378 343Q372 371 358 385T334 402T308 404Q263 404 229 370Q202 343 195 315T187 232V168V108Q187 78 188 68T191 55T200 49Q221 46 249 46H265V0H257L234 1Q210 2 183 2T145 3Q42 3 33 0H25V46H41Z"></path><path id="MJX-28-TEX-N-64" d="M376 495Q376 511 376 535T377 568Q377 613 367 624T316 637H298V660Q298 683 300 683L310 684Q320 685 339 686T376 688Q393 689 413 690T443 693T454 694H457V390Q457 84 458 81Q461 61 472 55T517 46H535V0Q533 0 459 -5T380 -11H373V44L365 37Q307 -11 235 -11Q158 -11 96 50T34 215Q34 315 97 378T244 442Q319 442 376 393V495ZM373 342Q328 405 260 405Q211 405 173 369Q146 341 139 305T131 211Q131 155 138 120T173 59Q203 26 251 26Q322 26 373 103V342Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mstyle"><g data-mml-node="mspace"></g></g><g data-mml-node="mo" transform="translate(278,0)"><use data-c="27F9" xlink:href="#MJX-28-TEX-N-27F9"></use></g><g data-mml-node="mstyle" transform="translate(1916,0)"><g data-mml-node="mspace"></g></g><g data-mml-node="mtext" transform="translate(2471.8,0)"><use data-c="73" xlink:href="#MJX-28-TEX-N-73"></use><use data-c="65" xlink:href="#MJX-28-TEX-N-65" transform="translate(394,0)"></use><use data-c="61" xlink:href="#MJX-28-TEX-N-61" transform="translate(838,0)"></use><use data-c="72" xlink:href="#MJX-28-TEX-N-72" transform="translate(1338,0)"></use><use data-c="63" xlink:href="#MJX-28-TEX-N-63" transform="translate(1730,0)"></use><use data-c="68" xlink:href="#MJX-28-TEX-N-68" transform="translate(2174,0)"></use><use data-c="28" xlink:href="#MJX-28-TEX-N-28" transform="translate(2730,0)"></use><use data-c="6B" xlink:href="#MJX-28-TEX-N-6B" transform="translate(3119,0)"></use><use data-c="29" xlink:href="#MJX-28-TEX-N-29" transform="translate(3647,0)"></use><use data-c="20" xlink:href="#MJX-28-TEX-N-20" transform="translate(4036,0)"></use><use data-c="2D" xlink:href="#MJX-28-TEX-N-2D" transform="translate(4286,0)"></use><use data-c="3E" xlink:href="#MJX-28-TEX-N-3E" transform="translate(4619,0)"></use><use data-c="20" xlink:href="#MJX-28-TEX-N-20" transform="translate(5397,0)"></use><use data-c="62" xlink:href="#MJX-28-TEX-N-62" transform="translate(5647,0)"></use><use data-c="6F" xlink:href="#MJX-28-TEX-N-6F" transform="translate(6203,0)"></use><use data-c="6F" xlink:href="#MJX-28-TEX-N-6F" transform="translate(6703,0)"></use><use data-c="6C" xlink:href="#MJX-28-TEX-N-6C" transform="translate(7203,0)"></use><use data-c="20" xlink:href="#MJX-28-TEX-N-20" transform="translate(7481,0)"></use><use data-c="66" xlink:href="#MJX-28-TEX-N-66" transform="translate(7731,0)"></use><use data-c="6F" xlink:href="#MJX-28-TEX-N-6F" transform="translate(8037,0)"></use><use data-c="75" xlink:href="#MJX-28-TEX-N-75" transform="translate(8537,0)"></use><use data-c="6E" xlink:href="#MJX-28-TEX-N-6E" transform="translate(9093,0)"></use><use data-c="64" xlink:href="#MJX-28-TEX-N-64" transform="translate(9649,0)"></use></g></g></g></svg></mjx-container><script type="math/tex">\implies \text{search(k) -> bool found}</script></p> <blockquote><p>之所以能够在 <code>第一次发现解</code>后 <code>判定该解就是最优解</code>并 <code>终止算法</code>是取决于 <code>题目性质</code></p> <p>如果 <code>题目所求的最优解</code> 与 <code>递归的深度</code>（也就是<code>最优解和长度无关</code>）无关，那么 <code>IDDFS</code>可能并不会更有效。</p> </blockquote> </li> <li><p>若<code>第一次发现任何解</code>则 <code>立即终止搜索</code>并 <code>返回该解</code> ， 否则报告 <code>无解</code></p> </li> </ul> <p> </p> <h3>Solution</h3> <h4>DFS</h4> <h5>Source</h5> <pre><code class="language-java" lang="java"> public static int f(int i) { return 3 * i; } public static int g(int i) { return i / 2; } public static String ans_string; public static void solve(int n, int m, int limit, String ops) { // Base Case if ((n == m) || (n == 0) || (m == 0) || (ops.length() > ans_string.length()) || limit >= 30) { if (n == m) { if (ops.length() < ans_string.length()) { ans_string = ops; } } return; } // Recursion Case solve(f(n), m, limit + 1, "f" + ops); solve(g(n), m, limit + 1, "g" + ops); } </code></pre> <h5>Benchmark</h5> <pre><code class="language-yaml" lang="yaml">----------------------------------------------------- Current Case: FUNC0.in & FUNC0.out Expected Input: [15 4] Expected Output: [4, gfgg] Your Output: [4, gfgg] Time Cost: 157.343000 ms (157343000 ns) Accepted. ----------------------------------------------------- Current Case: FUNC1.in & FUNC1.out Expected Input: [115 8] Expected Output: [9, gggggggff] Your Output: [9, gggggggff] Time Cost: 3852.005300 ms (3852005300 ns) Accepted. ----------------------------------------------------- Current Case: FUNC10.in & FUNC10.out Expected Input: [11838 127878] Expected Output: [25, ggffffggggfgggfffffgggggf] Your Output: [25, ggffffggggfgggfffffgggggf] Time Cost: 15302.874100 ms (15302874100 ns) Accepted. ----------------------------------------------------- Current Case: FUNC2.in & FUNC2.out Expected Input: [82 54] Expected Output: [8, fffggggg] Your Output: [8, fffggggg] Time Cost: 295.231800 ms (295231800 ns) Accepted. ----------------------------------------------------- Current Case: FUNC3.in & FUNC3.out Expected Input: [56 125] Expected Output: [22, ggggggffffffgggggggfff] Your Output: [22, ggggggffffffgggggggfff] Time Cost: 3743.782100 ms (3743782100 ns) Accepted. ----------------------------------------------------- Current Case: FUNC4.in & FUNC4.out Expected Input: [115 111] Expected Output: [18, fgfgfgggggfffggggf] Your Output: [18, fgfgfgggggfffggggf] Time Cost: 13528.005700 ms (13528005700 ns) Accepted. ----------------------------------------------------- Current Case: FUNC5.in & FUNC5.out Expected Input: [210 24907] Expected Output: [24, gffgggggfffffffffggggggf] Your Output: [24, gffgggggfffffffffggggggf] Time Cost: 14796.151600 ms (14796151600 ns) Accepted. ----------------------------------------------------- Current Case: FUNC6.in & FUNC6.out Expected Input: [50961 91791] Expected Output: [25, fggffffgggggggggggggfffff] Your Output: [25, fggffffgggggggggggggfffff] Time Cost: 2660.372100 ms (2660372100 ns) Accepted. ----------------------------------------------------- Current Case: FUNC7.in & FUNC7.out Expected Input: [59338 486] Expected Output: [22, fffffggggggggggggggggf] Your Output: [22, fffffggggggggggggggggf] Time Cost: 2700.998700 ms (2700998700 ns) Accepted. ----------------------------------------------------- Current Case: FUNC8.in & FUNC8.out Expected Input: [53530 750062539] Expected Output: [25, gfgfgfffffffffggfgggggfff] Your Output: [25, gfgfgfffffffffggfgggggfff] Time Cost: 5185.903400 ms (5185903400 ns) Accepted. ----------------------------------------------------- Current Case: FUNC9.in & FUNC9.out Expected Input: [96418 37529284] Expected Output: [25, gffffffgggggggggggfffffff] Your Output: [25, gffffffgggggggggggfffffff] Time Cost: 2065.022700 ms (2065022700 ns) Accepted. ----------------------------------------------------- Result Statistics: √ √ √ √ √ √ √ √ √ √ √ </code></pre> <h4>Iterative Deepening DFS</h4> <h5>Source</h5> <pre><code class="language-java" lang="java"> public static int f(int i) { return 3 * i; } public static int g(int i) { return i / 2; } /* Global Variable */ private static int n; private static int m; private static int k; private static boolean[] performF; public static int estimate(int n, int m) { return n; } public static boolean found() { int value = n; for (int i = 0; i < k; i++) { if (performF[i]) { value = f(value); } else value = g(value); } return value == m; } public static void printCurrentPlan() { for (int i = k - 1; i >= 0; i--) { System.out.print(performF[i] ? "f" : "g"); } } public static boolean search(int depth) { /* Base Case */ if (depth >= k) { return found(); } /* Recursion Case */ // At any depth, we can have 2 choices: /* Perform f */ performF[depth] = true; if (search(depth + 1)) { return true; } /* Perform g */ performF[depth] = false; if (search(depth + 1)) { return true; } // If we can't perform either f or g, we backtrack return false; } public static void solve(Scanner scanner) { n = scanner.nextInt(); m = scanner.nextInt(); int estimate = estimate(n, m); performF = new boolean[estimate + 1]; /* K-Search */ // k means perform tiems for (k = 0; k <= estimate; k++) { if (search(0)) { System.out.println(k); printCurrentPlan(); break; } } } </code></pre> <h5>Benchmark</h5> <pre><code class="language-yaml" lang="yaml">----------------------------------------------------- Current Case: FUNC0.in & FUNC0.out Expected Input: [15 4] Expected Output: [4, gfgg] Your Output: [4, gfgg] Time Cost: 3.844700 ms (3844700 ns) Accepted. ----------------------------------------------------- Current Case: FUNC1.in & FUNC1.out Expected Input: [115 8] Expected Output: [9, gggggggff] Your Output: [9, gggggggff] Time Cost: 1.549000 ms (1549000 ns) Accepted. ----------------------------------------------------- Current Case: FUNC10.in & FUNC10.out Expected Input: [11838 127878] Expected Output: [25, ggffffggggfgggfffffgggggf] Your Output: [25, ggffffggggfgggfffffgggggf] Time Cost: 2137.224700 ms (2137224700 ns) Accepted. ----------------------------------------------------- Current Case: FUNC2.in & FUNC2.out Expected Input: [82 54] Expected Output: [8, fffggggg] Your Output: [8, fffggggg] Time Cost: 0.945200 ms (945200 ns) Accepted. ----------------------------------------------------- Current Case: FUNC3.in & FUNC3.out Expected Input: [56 125] Expected Output: [22, ggggggffffffgggggggfff] Your Output: [22, ggggggffffffgggggggfff] Time Cost: 193.517300 ms (193517300 ns) Accepted. ----------------------------------------------------- Current Case: FUNC4.in & FUNC4.out Expected Input: [115 111] Expected Output: [18, fgfgfgggggfffggggf] Your Output: [18, fgfgfgggggfffggggf] Time Cost: 16.105000 ms (16105000 ns) Accepted. ----------------------------------------------------- Current Case: FUNC5.in & FUNC5.out Expected Input: [210 24907] Expected Output: [24, gffgggggfffffffffggggggf] Your Output: [24, gffgggggfffffffffggggggf] Time Cost: 1017.764000 ms (1017764000 ns) Accepted. ----------------------------------------------------- Current Case: FUNC6.in & FUNC6.out Expected Input: [50961 91791] Expected Output: [25, fggffffgggggggggggggfffff] Your Output: [25, fggffffgggggggggggggfffff] Time Cost: 1749.323400 ms (1749323400 ns) Accepted. ----------------------------------------------------- Current Case: FUNC7.in & FUNC7.out Expected Input: [59338 486] Expected Output: [22, fffffggggggggggggggggf] Your Output: [22, fffffggggggggggggggggf] Time Cost: 256.666400 ms (256666400 ns) Accepted. ----------------------------------------------------- Current Case: FUNC8.in & FUNC8.out Expected Input: [53530 750062539] Expected Output: [25, gfgfgfffffffffggfgggggfff] Your Output: [25, gfgfgfffffffffggfgggggfff] Time Cost: 1587.514600 ms (1587514600 ns) Accepted. ----------------------------------------------------- Current Case: FUNC9.in & FUNC9.out Expected Input: [96418 37529284] Expected Output: [25, gffffffgggggggggggfffffff] Your Output: [25, gffffffgggggggggggfffffff] Time Cost: 1395.128700 ms (1395128700 ns) Accepted. ----------------------------------------------------- Result Statistics: √ √ √ √ √ √ √ √ √ √ √ </code></pre> <h2>Computation without Priority Problem</h2> <h3>Description</h3> <p>给定 n 个正整数和 4 个运算符＋、－、∗、/，且运算符无优先级，如 2+3∗5=25。对于 任意给定的整数 m，试设计一个算法，用以上给出的 n 个数和 4 个运算符，产生整数 m， 且用的运算次数最少。给出的 n 个数中每个数最多只能用 1 次，但每种运算符可以任意使用。</p> <h3>Input</h3> <p>对于给定的 n 个正整数，设计一个算法，用最少的无优先级运算次数产生整数 m。</p> <h3>Output</h3> <p>由文件 input.txt 给出输入数据。第一行有 2 个正整数 n 和 m。第 2 行是给定的用于运算 的 n 个正整数。</p> <h3>Sample</h3> <p><strong>输入文件示例</strong></p> <p>input.txt</p> <p>5 25 5 2 3 6 7</p> <p><strong>输出文件示例</strong></p> <p>output.txt</p> <p>2 2+3*5</p> <h3>Analysis</h3> <h4>DFS</h4> <p>我们给出该问题的 <code>BFS Method</code>，该解法使用 <code>Token</code>存储 <code>已使用的数字</code>和 <code>参与运算的运算符</code>信息。</p> <p><code>递归过程</code>维护 <code>Token的链表</code>，通过 <code>遍历Token链表</code>来获得一个 <code>运算方案</code>。</p> <h4>IDDFS</h4> <p>不同于 <code>Integer Transformation Problem</code>的 <code>递归过程</code>：在 <code>DFS树</code>的 <code>每一层</code>只需要选择 <code>转变方法</code></p> <p><code>Computation without Priority Problem</code>的 <code>递归过程</code>：在 <code>DFS树</code>的 <code>每一层</code> 不但要选择 <code>使用的数字</code>，还要选择 <code>使用的运算符</code></p> <blockquote><p>不过，这并没有什么不同。因为，我们使用的是 <code>回溯法</code>。</p> <p>我们只管 <code>尝试所有可能的选法</code>，如果最终 <code>发现</code>确实 <code>DFS树的某层的选择</code>确实是错的，</p> <p>那么我们进行 <code>回溯</code>即可！然后继续寻找 <code>问题的解</code></p> </blockquote> <blockquote><p>另外，这里我们不讨论 <code>剪枝</code>的问题，尽管使用 <code>剪枝</code>可以再进一步优化该方法。</p> </blockquote> <h3>Solution</h3> <h4>BFS</h4> <h5>Source</h5> <pre><code class="language-java" lang="java"> enum Operators { ADDICTION("+"), SUBTRACTION("-"), MULTIPLICATION("*"), DIVISION("/"), NONE(""); private final String operatorString; Operators(String operatorString) { this.operatorString = operatorString; } public String toString() { return this.operatorString; } } static class Token { public Token parent; public int value; public int operand; public String operator; public int length; public Token(Token parent, int value, int operand, String operator) { this.parent = parent; this.value = value; this.operand = operand; this.operator = operator; this.length = parent != null ? parent.length + 1 : 1; } public ArrayList<Integer> listUsedOperands() { ArrayList<Integer> operands = new ArrayList<>(); Token current = this; while (current != null) { operands.add(current.operand); current = current.parent; } return operands; } public String getPath() { StringBuilder sb = new StringBuilder(); getPath(sb, this); return sb.toString(); } private void getPath(StringBuilder sb, Token currentToken) { if (currentToken != null) { getPath(sb, currentToken.parent); sb.append(currentToken.operator).append(currentToken.operand); } } @Override public String toString() { return this.getPath(); } } /* Current Case: ARIT0.in & ARIT0.out Expected Input: [5 25, 5 2 3 6 7] Expected Output: [2, 2+3*5] 5 2 3 6 7 0 0 0 0 0 */ public static Token solve(ArrayList<Integer> nums, int m) { /* Initialize the tokens */ LinkedList<Token> tokens = new LinkedList<>(); for (int num : nums) { // If we are lucky enough... if (num == m) return new Token(null, m, m, Operators.NONE.toString()); tokens.add(new Token(null, num, num, Operators.NONE.toString())); } /* Brute-Force-Search */ for (int level = 0; level < nums.size(); level++) { int SIZE = tokens.size(); for (int amount = 0; amount < SIZE; amount++) { /* Get the first token */ Token currentToken = tokens.poll(); /* Generate tokens */ // Get unused nums ArrayList<Integer> unusedNums = new ArrayList<>(nums); currentToken.listUsedOperands().forEach(unusedNums::remove); // Try all operators for (int num : unusedNums) { for (Operators operator : Operators.values()) { if (operator == Operators.NONE) continue; int newValue; switch (operator) { case ADDICTION: newValue = currentToken.value + num; break; case SUBTRACTION: newValue = currentToken.value - num; break; case MULTIPLICATION: newValue = currentToken.value * num; break; case DIVISION: newValue = currentToken.value / num; break; default: newValue = 0xdead; } /* Push */ Token newToken = new Token(currentToken, newValue, num, operator.toString()); /* Found ? */ if (newToken.value == m) { return newToken; } else tokens.add(newToken); } } } } return null; } </code></pre> <h5>Benchmark</h5> <pre><code class="language-yaml" lang="yaml">----------------------------------------------------- Current Case: ARIT0.in & ARIT0.out Expected Input: [5 25, 5 2 3 6 7] Expected Output: [2, 2+3*5] Your Output: [2, 2+3*5] Time Cost: 7.099500 ms (7099500 ns) Accepted. ----------------------------------------------------- Current Case: ARIT1.in & ARIT1.out Expected Input: [30 2894, 2 40 2 50 48 23 39 26 23 42 36 29 35 17 39 16 48 12 45 20 35 19 20 3 15 42 1 49 45 10 ] Expected Output: [3, 40+39*36+50] Your Output: [3, 40+39*36+50] Time Cost: 477.980500 ms (477980500 ns) Accepted. ----------------------------------------------------- Current Case: ARIT10.in & ARIT10.out Expected Input: [6 721, 1 2 3 4 5 6] Expected Output: [5, 2*3*4*5*6+1] Your Output: [5, 2*3*4*5*6+1] Time Cost: 38.360500 ms (38360500 ns) Accepted. ----------------------------------------------------- Current Case: ARIT2.in & ARIT2.out Expected Input: [21 11573, 16 17 3 12 24 49 25 18 28 5 38 8 22 3 11 11 16 21 4 11 32 ] Expected Output: [4, 16+3*38*16+21] Your Output: [4, 16*17+32*38+21] Time Cost: 7109.397600 ms (7109397600 ns) Wrong Answer. ----------------------------------------------------- Current Case: ARIT3.in & ARIT3.out Expected Input: [8 1554, 32 23 1 1 26 33 28 5 ] Expected Output: [3, 33+28*26-32] Your Output: [3, 33+28*26-32] Time Cost: 3.193600 ms (3193600 ns) Accepted. ----------------------------------------------------- Current Case: ARIT4.in & ARIT4.out Expected Input: [41 48, 34 44 38 38 28 38 39 45 34 19 13 4 36 41 32 30 8 31 10 15 32 27 34 38 4 42 35 49 23 27 18 30 9 6 2 47 47 16 48 9 17 ] Expected Output: [0, 48] Your Output: [0, 48] Time Cost: 1.859300 ms (1859300 ns) Accepted. ----------------------------------------------------- Current Case: ARIT5.in & ARIT5.out Expected Input: [17 11787, 3 9 37 7 7 11 32 48 34 3 31 20 27 38 19 27 17 ] Expected Output: [3, 31*20*19+7] Your Output: [3, 31*20*19+7] Time Cost: 47.619500 ms (47619500 ns) Accepted. ----------------------------------------------------- Current Case: ARIT6.in & ARIT6.out Expected Input: [4 24, 1 1 10 7] Expected Output: [3, 1+1*7+10] Your Output: [3, 1+1*7+10] Time Cost: 1.087000 ms (1087000 ns) Accepted. ----------------------------------------------------- Current Case: ARIT7.in & ARIT7.out Expected Input: [18 2553, 32 48 3 42 7 34 12 29 3 50 30 35 22 13 35 9 11 20 ] Expected Output: [3, 32+29*42-9] Your Output: [3, 32+29*42-9] Time Cost: 3.876700 ms (3876700 ns) Accepted. ----------------------------------------------------- Current Case: ARIT8.in & ARIT8.out Expected Input: [6 1234, 1 2 3 4 5 6] Expected Output: [No Solution!] Your Output: [No Solution!] Time Cost: 1250.530200 ms (1250530200 ns) Accepted. ----------------------------------------------------- Current Case: ARIT9.in & ARIT9.out Expected Input: [27 9546, 10 5 30 1 14 49 8 19 44 21 23 35 26 7 35 3 27 18 5 15 49 23 8 44 48 49 47 ] Expected Output: [4, 10+14*19*21-30] Your Output: [4, 10*30-26*35-44] Time Cost: 33963.559100 ms (33963559100 ns) Wrong Answer. ----------------------------------------------------- Result Statistics: √ √ √ × √ √ √ √ √ √ × </code></pre> <h4>Iterative-Deeping DFS</h4> <h5>Source</h5> <pre><code class="language-java" lang="java"> /* Global Variables */ private enum Operators { ADDICTION("+"), SUBTRACTION("-"), MULTIPLICATION("*"), DIVISION("/"); private final String operatorString; Operators(String operatorString) { this.operatorString = operatorString; } @Override public String toString() { return this.operatorString; } } private static int k; private static int n; private static int m; private static int[] nums; private static boolean[] used; private static int[] operands; private static int[] operators; public static void printCurrentPlan() { // for n numbers, we can use k \in {0, 1, 2, ..., n-1} operators // k = 0 means that we don't need to use any operators for (int i = 0; i <= k; i++) { if (i > 0) System.out.print(Operators.values()[operators[i - 1]]); System.out.print(operands[i]); } } public static boolean found() { int sum = 0xdead; // k means the number of operands for (int i = 0; i <= k; i++) { // Push the first operand if (i == 0) { sum = operands[0]; continue; } // Actually, we won't use the last index of operator // And if we only have one operand, we won't need to calc any operators. (just ignore the only operator at index 0) int operator = operators[i - 1]; int operand = operands[i]; // Calculate switch (Operators.values()[operator]) { case ADDICTION: sum += operand; break; case SUBTRACTION: sum -= operand; break; case MULTIPLICATION: sum *= operand; break; case DIVISION: sum /= operand; break; } } return sum == m; } public static boolean search(int depth) { /* Base Case */ if (depth > k) { return found(); } /* Recursive Case */ // We can choose any of the unused numbers ! for (int i = 0; i < nums.length; i++) { // Skip the number if we have used it. if (used[i]) continue; else used[i] = true; // Use the number operands[depth] = nums[i]; // Also, we can use any of the operators ! for (int j = 0; j < Operators.values().length; j++) { // Use the operator operators[depth] = Operators.values()[j].ordinal(); // Go ! if (search(depth + 1)) { // if not found, the recursion should go ahead return true; } } // Free it ! used[i] = false; } return false; } public static void solve(Scanner scanner) { /* Initialize */ n = scanner.nextInt(); nums = new int[n]; used = new boolean[n]; operands = new int[n]; operators = new int[n]; m = scanner.nextInt(); for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } /* k-search */ // k is the number of operands // for n, k = 0, 1, 2, ..., n-1 for (k = 0; k < nums.length; k++) { if (search(0)) { System.out.println(k); printCurrentPlan(); return; } } System.out.println("No Solution!"); } </code></pre> <h5>Benchmark</h5> <pre><code class="language-yaml" lang="yaml">----------------------------------------------------- Current Case: ARIT0.in & ARIT0.out Expected Input: [5 25, 5 2 3 6 7] Expected Output: [2, 2+3*5] Your Output: [2, 2+3*5] Time Cost: 6.820100 ms (6820100 ns) Accepted. ----------------------------------------------------- Current Case: ARIT1.in & ARIT1.out Expected Input: [30 2894, 2 40 2 50 48 23 39 26 23 42 36 29 35 17 39 16 48 12 45 20 35 19 20 3 15 42 1 49 45 10 ] Expected Output: [3, 40+39*36+50] Your Output: [3, 40+39*36+50] Time Cost: 473.039600 ms (473039600 ns) Accepted. ----------------------------------------------------- Current Case: ARIT10.in & ARIT10.out Expected Input: [6 721, 1 2 3 4 5 6] Expected Output: [5, 2*3*4*5*6+1] Your Output: [5, 2*3*4*5*6+1] Time Cost: 266.458500 ms (266458500 ns) Accepted. ----------------------------------------------------- Current Case: ARIT2.in & ARIT2.out Expected Input: [21 11573, 16 17 3 12 24 49 25 18 28 5 38 8 22 3 11 11 16 21 4 11 32 ] Expected Output: [4, 16+3*38*16+21] Your Output: [4, 16+3*38*16+21] Time Cost: 2210.722500 ms (2210722500 ns) Accepted. ----------------------------------------------------- Current Case: ARIT3.in & ARIT3.out Expected Input: [8 1554, 32 23 1 1 26 33 28 5 ] Expected Output: [3, 33+28*26-32] Your Output: [3, 33+28*26-32] Time Cost: 17.388700 ms (17388700 ns) Accepted. ----------------------------------------------------- Current Case: ARIT4.in & ARIT4.out Expected Input: [41 48, 34 44 38 38 28 38 39 45 34 19 13 4 36 41 32 30 8 31 10 15 32 27 34 38 4 42 35 49 23 27 18 30 9 6 2 47 47 16 48 9 17 ] Expected Output: [0, 48] Your Output: [0, 48] Time Cost: 1.912900 ms (1912900 ns) Accepted. ----------------------------------------------------- Current Case: ARIT5.in & ARIT5.out Expected Input: [17 11787, 3 9 37 7 7 11 32 48 34 3 31 20 27 38 19 27 17 ] Expected Output: [3, 31*20*19+7] Your Output: [3, 31*20*19+7] Time Cost: 510.196400 ms (510196400 ns) Accepted. ----------------------------------------------------- Current Case: ARIT6.in & ARIT6.out Expected Input: [4 24, 1 1 10 7] Expected Output: [3, 1+1*7+10] Your Output: [3, 1+1*7+10] Time Cost: 1.734900 ms (1734900 ns) Accepted. ----------------------------------------------------- Current Case: ARIT7.in & ARIT7.out Expected Input: [18 2553, 32 48 3 42 7 34 12 29 3 50 30 35 22 13 35 9 11 20 ] Expected Output: [3, 32+29*42-9] Your Output: [3, 32+29*42-9] Time Cost: 17.189900 ms (17189900 ns) Accepted. ----------------------------------------------------- Current Case: ARIT8.in & ARIT8.out Expected Input: [6 1234, 1 2 3 4 5 6] Expected Output: [No Solution!] Your Output: [No Solution!] Time Cost: 293.963800 ms (293963800 ns) Accepted. ----------------------------------------------------- Current Case: ARIT9.in & ARIT9.out Expected Input: [27 9546, 10 5 30 1 14 49 8 19 44 21 23 35 26 7 35 3 27 18 5 15 49 23 8 44 48 49 47 ] Expected Output: [4, 10+14*19*21-30] Your Output: [4, 10+14*19*21-30] Time Cost: 5940.226300 ms (5940226300 ns) Accepted. ----------------------------------------------------- Result Statistics: √ √ √ √ √ √ √ √ √ √ √ </code></pre> <p> </p>{% endraw %}