c++ - 使用资源和锁进行 A* 搜索
问题描述
考虑资源和锁的路径优化问题。我们得到一个加权无向图，目标是尽可能便宜地从给定的起始顶点到给定的目标顶点。这里的问题是一些顶点被阻塞了，可以在这里看到问题并且只有代理携带适当的资源（key）才能解除阻塞，可以在图的其他顶点找到（也可能是否被阻止）。
使用 A* 搜索来选择具有最佳即时启发式价值的移动。
我在 a* 搜索中尝试了很多代码。但我不明白如何用密钥和资源编写它。你能帮帮我吗？
下面是我尝试过的 a* 搜索的代码。但是里面没有锁和钥匙。我需要帮助来编码，包括锁和钥匙。
void aStarSearch(int grid[][COL], Pair src, Pair dest)
{
// If the source is out of range
if (isValid (src.first, src.second) == false)
{
printf ("Source is invalid\n");
return;
}
// If the destination is out of range
if (isValid (dest.first, dest.second) == false)
{
printf ("Destination is invalid\n");
return;
}
// Either the source or the destination is blocked
if (isUnBlocked(grid, src.first, src.second) == false ||
isUnBlocked(grid, dest.first, dest.second) == false)
{
printf ("Source or the destination is blocked\n");
return;
}
// If the destination cell is the same as source cell
if (isDestination(src.first, src.second, dest) == true)
{
printf ("We are already at the destination\n");
return;
}
// Create a closed list and initialise it to false which means
// that no cell has been included yet
// This closed list is implemented as a boolean 2D array
bool closedList[ROW][COL];
memset(closedList, false, sizeof (closedList));
// Declare a 2D array of structure to hold the details
//of that cell
cell cellDetails[ROW][COL];
int i, j;
for (i=0; i<ROW; i++)
{
for (j=0; j<COL; j++)
{
cellDetails[i][j].f = FLT_MAX;
cellDetails[i][j].g = FLT_MAX;
cellDetails[i][j].h = FLT_MAX;
cellDetails[i][j].parent_i = -1;
cellDetails[i][j].parent_j = -1;
}
}
// Initialising the parameters of the starting node
i = src.first, j = src.second;
cellDetails[i][j].f = 0.0;
cellDetails[i][j].g = 0.0;
cellDetails[i][j].h = 0.0;
cellDetails[i][j].parent_i = i;
cellDetails[i][j].parent_j = j;
/*
Create an open list having information as-
<f, <i, j>>
where f = g + h,
and i, j are the row and column index of that cell
Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
This open list is implenented as a set of pair of pair.*/
set<pPair> openList;
// Put the starting cell on the open list and set its
// 'f' as 0
openList.insert(make_pair (0.0, make_pair (i, j)));
// We set this boolean value as false as initially
// the destination is not reached.
bool foundDest = false;
while (!openList.empty())
{
pPair p = *openList.begin();
// Remove this vertex from the open list
openList.erase(openList.begin());
// Add this vertex to the closed list
i = p.second.first;
j = p.second.second;
closedList[i][j] = true;
/*
Generating all the 8 successor of this cell
N.W N N.E
\ | /
\ | /
W----Cell----E
/ | \
/ | \
S.W S S.E
Cell-->Popped Cell (i, j)
N --> North (i-1, j)
S --> South (i+1, j)
E --> East (i, j+1)
W --> West (i, j-1)
N.E--> North-East (i-1, j+1)
N.W--> North-West (i-1, j-1)
S.E--> South-East (i+1, j+1)
S.W--> South-West (i+1, j-1)*/
// To store the 'g', 'h' and 'f' of the 8 successors
double gNew, hNew, fNew;
//----------- 1st Successor (North) ------------
// Only process this cell if this is a valid one
if (isValid(i-1, j) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i-1, j, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j].parent_i = i;
cellDetails[i-1][j].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j] == false &&
isUnBlocked(grid, i-1, j) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue (i-1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j].f == FLT_MAX ||
cellDetails[i-1][j].f > fNew)
{
openList.insert( make_pair(fNew,
make_pair(i-1, j)));
// Update the details of this cell
cellDetails[i-1][j].f = fNew;
cellDetails[i-1][j].g = gNew;
cellDetails[i-1][j].h = hNew;
cellDetails[i-1][j].parent_i = i;
cellDetails[i-1][j].parent_j = j;
}
}
}
//----------- 2nd Successor (South) ------------
// Only process this cell if this is a valid one
if (isValid(i+1, j) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j].parent_i = i;
cellDetails[i+1][j].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j] == false &&
isUnBlocked(grid, i+1, j) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i+1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j].f == FLT_MAX ||
cellDetails[i+1][j].f > fNew)
{
openList.insert( make_pair (fNew, make_pair (i+1, j)));
// Update the details of this cell
cellDetails[i+1][j].f = fNew;
cellDetails[i+1][j].g = gNew;
cellDetails[i+1][j].h = hNew;
cellDetails[i+1][j].parent_i = i;
cellDetails[i+1][j].parent_j = j;
}
}
}
//----------- 3rd Successor (East) ------------
// Only process this cell if this is a valid one
if (isValid (i, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i][j+1].parent_i = i;
cellDetails[i][j+1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j+1] == false &&
isUnBlocked (grid, i, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue (i, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i][j+1].f == FLT_MAX ||
cellDetails[i][j+1].f > fNew)
{
openList.insert( make_pair(fNew,
make_pair (i, j+1)));
// Update the details of this cell
cellDetails[i][j+1].f = fNew;
cellDetails[i][j+1].g = gNew;
cellDetails[i][j+1].h = hNew;
cellDetails[i][j+1].parent_i = i;
cellDetails[i][j+1].parent_j = j;
}
}
}
//----------- 4th Successor (West) ------------
// Only process this cell if this is a valid one
if (isValid(i, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i][j-1].parent_i = i;
cellDetails[i][j-1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j-1] == false &&
isUnBlocked(grid, i, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i][j-1].f == FLT_MAX ||
cellDetails[i][j-1].f > fNew)
{
openList.insert( make_pair (fNew,
make_pair (i, j-1)));
// Update the details of this cell
cellDetails[i][j-1].f = fNew;
cellDetails[i][j-1].g = gNew;
cellDetails[i][j-1].h = hNew;
cellDetails[i][j-1].parent_i = i;
cellDetails[i][j-1].parent_j = j;
}
}
}
//----------- 5th Successor (North-East) ------------
// Only process this cell if this is a valid one
if (isValid(i-1, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i-1, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j+1].parent_i = i;
cellDetails[i-1][j+1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j+1] == false &&
isUnBlocked(grid, i-1, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i-1, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j+1].f == FLT_MAX ||
cellDetails[i-1][j+1].f > fNew)
{
openList.insert( make_pair (fNew,
make_pair(i-1, j+1)));
// Update the details of this cell
cellDetails[i-1][j+1].f = fNew;
cellDetails[i-1][j+1].g = gNew;
cellDetails[i-1][j+1].h = hNew;
cellDetails[i-1][j+1].parent_i = i;
cellDetails[i-1][j+1].parent_j = j;
}
}
}
//----------- 6th Successor (North-West) ------------
// Only process this cell if this is a valid one
if (isValid (i-1, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination (i-1, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j-1].parent_i = i;
cellDetails[i-1][j-1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j-1] == false &&
isUnBlocked(grid, i-1, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i-1, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j-1].f == FLT_MAX ||
cellDetails[i-1][j-1].f > fNew)
{
openList.insert( make_pair (fNew, make_pair (i-1, j-1)));
// Update the details of this cell
cellDetails[i-1][j-1].f = fNew;
cellDetails[i-1][j-1].g = gNew;
cellDetails[i-1][j-1].h = hNew;
cellDetails[i-1][j-1].parent_i = i;
cellDetails[i-1][j-1].parent_j = j;
}
}
}
//----------- 7th Successor (South-East) ------------
// Only process this cell if this is a valid one
if (isValid(i+1, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j+1].parent_i = i;
cellDetails[i+1][j+1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j+1] == false &&
isUnBlocked(grid, i+1, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i+1, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j+1].f == FLT_MAX ||
cellDetails[i+1][j+1].f > fNew)
{
openList.insert(make_pair(fNew,
make_pair (i+1, j+1)));
// Update the details of this cell
cellDetails[i+1][j+1].f = fNew;
cellDetails[i+1][j+1].g = gNew;
cellDetails[i+1][j+1].h = hNew;
cellDetails[i+1][j+1].parent_i = i;
cellDetails[i+1][j+1].parent_j = j;
}
}
}
//----------- 8th Successor (South-West) ------------
// Only process this cell if this is a valid one
if (isValid (i+1, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j-1].parent_i = i;
cellDetails[i+1][j-1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j-1] == false &&
isUnBlocked(grid, i+1, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i+1, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j-1].f == FLT_MAX ||
cellDetails[i+1][j-1].f > fNew)
{
openList.insert(make_pair(fNew,
make_pair(i+1, j-1)));
// Update the details of this cell
cellDetails[i+1][j-1].f = fNew;
cellDetails[i+1][j-1].g = gNew;
cellDetails[i+1][j-1].h = hNew;
cellDetails[i+1][j-1].parent_i = i;
cellDetails[i+1][j-1].parent_j = j;
}
}
}
}
// When the destination cell is not found and the open
// list is empty, then we conclude that we failed to
// reach the destiantion cell. This may happen when the
// there is no way to destination cell (due to blockages)
if (foundDest == false)
printf("Failed to find the Destination Cell\n");
return;
}
解决方案
一个简单的解决方案（不确定是否最好）是这样的：
您有一个原始图 G，其中边缘可以锁定到 K 个可能的键。您可以通过分层图 G 的 2^K 个副本来生成新的图 G'，每个键组合一个，但根据层表示的键进行更改，以便边存在或不存在。（例如，假设一个图有两条走廊，一条带蓝色锁，一条带红色；K=2，所以我们需要制作 4 层：无键层、蓝色层、红色层和全键层。在no-key 层，两条走廊的边都不存在；all-key 层，它们都存在；蓝色和红色层，只有各自的边存在，而另一个不存在。）
这有效地将搜索状态从（位置）转换为（位置，库存），以便记住您携带的物品。（例如，不是像“锅炉房”这样的状态，现在您有像“拿着红色钥匙的锅炉房”这样的状态。）
然后，您可以在找到键的位置连接图层。如果无法删除键，则可以使用有向边；如果可以删除键，则可以使用双向边，或者您无需费心制作双向图。这样，每次找到一个键时，您都会“跳”到具有所有当前键的层，再加上新找到的键。（例如，在有红色钥匙的房间里，从无钥匙图的房间节点到红色图的房间节点，从蓝色图到全钥匙的节点。）
最后，将目标节点的所有副本作为最终副本。或者等效地，从目标节点的所有副本到原始无密钥层的目标节点创建一条零成本边。
如果您需要花费一把钥匙来解锁一扇门，而不是仅仅拥有它，您可以更改门边缘以将您放到拥有除与门对应的钥匙之外的所有钥匙的层。
如果一次只能携带一把钥匙，则不需要 2^K 份 G；仅 K+1 层就足够了（无键、红色、蓝色）。相应地更改边缘。
显然，这将搜索空间扩大了 2^K 倍，但搜索算法几乎没有变化，只有图本身。
如果您可以将密钥放在任意位置并期望再次找到它们，这将不再起作用。（如果您可以放下钥匙并在其原始生成点找到它们，它仍然可以工作。）
推荐阅读
- javascript - 链接到多个网站的按钮
- c# - WPF 按钮作为带有文本和矢量图标的自定义控件
- android - 无法更改 Theme.Holo.Light 操作栏的背景颜色
- c++ - c++ 中的时间计数根据命令的顺序而不是实际的进程更改输出
- php - 样式化和格式化 PHP 多维数组
- c# - C# 调试器文本可视化器输出与 Visual Studio 2019 中的控制台输出对齐
- android - 我怎么知道点击了哪个“TextView”
- angular - 身份验证保护重定向不适用于子路由
- php - sqlsrv_execute 不返回任何内容
- google-analytics - GA 的产品性能报告中如何计算产品详细信息视图？