设计一个解n后问题的优先队列式分支限界法

男娘i 2022-05-16 22:10 163阅读 0赞

using namespace std;

struct HeapNode\{  //定义一个结构体用来保存节点的行和列

int row;//行

int col;//列

\};

struct cmp\{  //自定义比较函数，在优先队列中将会用到，优先级的设定

bool operator()(HeapNode a,HeapNode b) \{

if(a.row==b.row)return a.col>b.col;//同一行的列号越小优先级越高

else return a.row<b.row;//不同行行号行号越大优先级越高

\}

\};

struct cmp \{  //自定义比较函数，在优先队列中将会用到，优先级的设定

bool operator()(HeapNode a, HeapNode b) \{

if (a.row == b.row)return a.col < b.col;//同一行的列号越小优先级越高

else

\{

if (a.row == b.row)return a.col < b.col;

else return a.row < b.row;//不同行行号行号越大优先级越高

\}

\}

\};

//priority\_queue为优先队列类模板,根据优先级（cmp）进行排列

void AddLiveNode(priority\_queue<HeapNode,vector<HeapNode>,cmp> &maximum\_heap,int i,int n)\{

HeapNode node;

for (int j = 1; j <= n; j++)\{

node.row=i;

node.col=j;

maximum\_heap.push(node);

\}

\}

bool place(int k,int \*track)\{

for (int j = 1; j < k; j++)\{

if ((abs(k - j) == abs(track\[j\]- track\[k\]) || (track\[j\]==track\[k\])))//前面的是检查是否在同一对角线上后面是是否在同一列上

return false;

\}

return true;

\}

bool nqueens(priority\_queue<HeapNode,vector<HeapNode>,cmp> &maximum\_heap,int n,int \*track)\{ //放置节点的过程

AddLiveNode(maximum\_heap,1,n);

int i=0;

do

\{

i=maximum\_heap.top().row;

/\*防止超过界限赋值，以避免指针越界。\*/

if(i !=n+1)

track\[i\]=maximum\_heap.top().col;//取队首元素

maximum\_heap.pop();//队首元素出队

/\*防止超过界限，以避免指针越界。\*/

if(i !=n+1)

\{

if(place(i,track))

AddLiveNode(maximum\_heap,i+1,n);

\}

if(maximum\_heap.empty()) return false;

\}while(i !=n+1);

while(!maximum\_heap.empty())

maximum\_heap.pop();

return true;

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读

相关分支限界法

一、分支限界法的基本思想　　在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一

绝地灬酷狼/ 2023年10月06日 09:41/ 0 赞/ 30 阅读

相关旅行商问题分析（分支限界法）

一、题目 ![1462891-20190923210503975-622218032.png][] 二、思路 1、dfs 实验要求用多种思路完

古城微笑少年丶/ 2023年08月17日 16:11/ 0 赞/ 116 阅读

相关装载问题 | 分支限界法（限上界）

> 装载问题：有n个集装箱要装上 2 艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑wi <= c1 + c2。 > > 问是否有一个合理的装载方案,可将这n

喜欢ヅ旅行/ 2023年02月10日 01:02/ 0 赞/ 21 阅读

相关分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题，并给出限界函数，并画出该实例的状态空间树。

目录回溯算法【0-1背包问题】分支界限算法【0-1背包问题】作业题（期末考试必考）小结 -------------------- > ![waterm

末蓝、/ 2022年12月25日 01:55/ 0 赞/ 252 阅读

相关算法设计与分析——分支限界法——n皇后问题

一、问题描述问题描述：在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n皇后问题等价于在n\n的棋盘上

秒速五厘米/ 2022年10月08日 14:21/ 0 赞/ 371 阅读

相关算法设计与分析——分支限界法——布线问题

印刷电路板将布线区域划分成n×m个方格如图a所示。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图b所示。为了避

傷城~/ 2022年10月07日 06:53/ 0 赞/ 196 阅读

相关算法设计与分析——分支限界法——装载问题

有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方

谁践踏了优雅/ 2022年10月05日 13:52/ 0 赞/ 201 阅读

相关回溯法与分支限界

回溯法 1、有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 2、回溯法的基本做法是搜索，或是一种组织得井井有条的，能

灰太狼/ 2022年09月25日 11:19/ 0 赞/ 256 阅读

相关 (C++)分支限界法求解背包问题

1.beibao.h文件代码如下： ifndef BEIBAO_H define BEIBAO_H include <math.h>

比眉伴天荒/ 2022年09月17日 11:19/ 0 赞/ 227 阅读

相关设计一个解n后问题的优先队列式分支限界法

using namespace std; struct HeapNode\{ //定义一个结构体用来保存节点的行和列 int row;//行 int col;

男娘i/ 2022年05月16日 22:10/ 0 赞/ 164 阅读