-
大小: 16KB文件類型: .rar金幣: 1下載: 0 次發布日期: 2021-01-05
- 語言: 其他
- 標簽:
資源簡介
一般解空間的隊列式分支限界法
Description
試設計一個用隊列式分支限界法搜索一般解空間的函數。該函數的參數包括結點可行性
判定函數和上界函數等必要的函數，并將此函數用于解布線問題。
印刷電路板將布線區域劃分成n×m個方格陣列如圖(a)所示。精確的電路布線問題要求
確定連接方格a的中點到方格b 的中點的最短布線方案。在布線時，電路只能沿直線或直角
布線，如圖(b)所示。為了避免線路相交，已布了線的方格做了封鎖標記，其它線路不允許
穿過被封鎖的方格。對于給定的布線區域，編程計算最短布線方案。
Input
由文件input.txt給出輸入數據。第一行有3 個正整數n，m，k，
代碼片段和文件信息
#include?
#include?
#include?
#include?
using?namespace?std;
ifstream?cin（“1.in“）;
ofstream?cout（“1.out“）;
struct?pos{
int?xy;
};
int?mnk;
pos?pspe;
vector??>?mv;
queue??Q;
bool?FindPath（）
{
if?（ps.x?==?pe.x?&&?ps.y?==?pe.y）
return?true;
pos?offset[4]={{01}{10}{0-1}{-10}};
pos?phpc;
ph?=?ps;
mv[ps.x][ps.y]?=?2;
do{
for（int?i?=?0;?i? {
pc.x?=?ph.x?+?offset[i].x;
pc.y?=?ph.y?+?offset[i].y;
if?（mv[pc.x][pc.y]?==?0）
{
mv[pc.x][pc.y]?=?mv[ph.x][ph.y]?+?1;
if?（pc.x?==?pe.x?&&?pc.y?==?pe.y）
break;
Q.push（pc）;
}
}
if（pc.x?==?pe.x?&&?pc.y?==?pe.y）
break;
if?（Q.empty（））
return?false;
ph.x?=?Q.front（）.x;
ph.y?=?Q.fr ?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????2055??2008-11-22?12:46??一般解空間的隊列式分支限界法\1127.cpp
?????文件??????36864??2009-03-13?19:21??一般解空間的隊列式分支限界法\一般解空間的隊列式分支限界法.doc
?????目錄??????????0??2009-03-13?19:22??一般解空間的隊列式分支限界法
-----------?---------??----------?-----??----
????????????????38919????????????????????3
評論
共有 條評論