Olay教授正在為一家石油公司咨詢,該公司正在計劃建造一條由東向西的石油主管道,該管道要穿過一片有n口井的油田,從每口井中都有一條噴油管沿最短路徑與主管道直接相連(噴油管道為南北方向)。 給定各個井的X坐標和Y坐標,Olay教授要如何才能選擇最佳主管道的位置(即:使各噴油管長度之和最?。??
對于符號三角問題,符號三角形的第一行有n個符號。符號可以為“+”或“-”,以下每一行的符號由上行得到,2個同號下面都是“+”,2個異號下面都是“-”。如下圖所示(第一行有4個符號的符號三角中的其中的一個): 請畫出使用回溯法求解第一行有4個符號(即n=4)時,解空間樹的形狀。
第一行4個符號(即n=4)時,解空間樹是一棵完全二叉樹。