使用图的字符串搜索算法? C ++ [英] String Searching Algorithm that uses a graph ? C++
问题描述
大家好.上面是我已分配的编码项目.我正在阅读说明，完全迷路了，因为我从未学过如何编写无向图?不确定教授如何期望我们做到这一点，但我希望可以从专家那里得到一些帮助.你们建议您阅读任何读物(或技巧)以熟悉如何开始使用该程序?谢谢，谢谢！
Hey guys. Above is a coding project I have been assigned. Im reading the instructions and am completely lost because I've never learned how to code an undirected graph? Not sure how my professor expects us to do this but I was hoping I could get some help from experts. Any readings (or tips) you guys suggest I can look at to familiarize myself with how to get started on the program? Appreciate it, thanks!
推荐答案
要解决的问题称为单词变形".您的讲师对使用无向图给出了一些限制，其中相邻节点与原点仅相差一个字符.不幸的是，这些要求还不够明确. 一个字符的区别是模棱两可的.如果我们使用replace-insert-delete惯用语，那么可以通过比较2个相等大小的字符串来使用其他功能.我认为是完整的方法.
The problem to solve is called "Word Morph". Your instructor gave some restrictions as to use an undirected graph, where the neighbour node differs only one character from the origin. Unfortuantely the requirements are not clear enough. "Differ by one character is ambiguous. If we use the replace-insert-delete idiom, then we can use other functions as by comparing 2 equal size strings. I assume the full approach.
最后，您需要通过图表找到最短的方法.
And, at the end, you need to find a shortest way through a graph.
我可以为您介绍一种可能的解决方案.一个完整的工作代码示例.
I could present you one possible solution. A complete working code example.
通过图的非加权方式，因为从一个节点到下一个节点的旅行成本始终为1.所以实际上，我们在谈论的是无向非加权图.
By the way the graph is non-weigthed, because the cost of travelling from one node to the next is always 1. So actually we are talking about an undirected non-weighted graph.
我们在这里需要使用的主要算法是:
The main algorithms we need using here are:
- 触角蛋白.计算2根琴弦的距离
- 和广度优先搜索"，以通过图形查找短路路径
请注意，如果单词的长度相同，则不需要Levensthein.只需逐个字符比较字符并计算差异即可.那很简单. (但是如前所述:指令有点不清楚)
Please note, If the words should have the same length, then no Levensthein is needed. Just compare character by charcter and count the differences. That's rather simple. (But as said: The instructions are a little bit unclear)
两种算法都可以修改.例如:您不需要Levensthein距离大于1.您可以在找到距离1后终止距离计算.而且，在广度优先搜索中，您可以显示前进的路径.
Both algorithms can be modified. For example: You do not need a Levensthein distance greater than 1. You can terminate the distance calculation after distance one has been found. And, in the breadth first search, you could show the path, through which you are going.
好的，现在，如何实现无向图.有两种可能性:
OK, now, how to implement an undirected graph. There are 2 possibilities:
- 矩阵(我不会解释)
- 列表或向量
对于这种情况，我建议使用向量方法.矩阵会比较稀疏，因此向量更好.
I would recommend the vector approach for this case. A matrix would be rather sparse, so, better a vector.
您需要的基本数据结构是一个包含顶点和邻居的节点.因此，您将单词(a std::string)作为顶点，并将其作为邻居".那是图形中其他节点的索引位置的std::vector.
The basic data structure that you need is a node containing vertices and neighbours. So you have the word (a std::string) as vertex and the "neighbours". That is a std::vector of index positions to other nodes in the graph.
图是节点的向量.并且节点邻居指向此向量中的其他节点.我们使用向量中的索引来表示邻居.所有这些我们打包成一个结构，并将其称为"UndirectedGraph".我们添加了一个构建"功能来检查相邻性.在该函数中，我们将每个字符串与任何字符串进行比较，并检查差异是否小于2，因此0或1.0表示相等，而1是给定的约束.如果发现这种差异，则将其添加为相应节点中的邻居.
The graph is a vector of nodes. And nodes neighbours point to other nodes in this vector. We use the index into the vector to denote neighbours. All this we pack into a structure and call it "UndirectedGraph". We add a "build" function that checks for adjacencies. In this function we compare each string with any and check, if the difference is <2, so 0 or 1. 0 means equeal and 1 is a given constraint. If we find such a difference, we add it as neighboour in the corresponding node.
此外，我们添加了广度优先搜索算法.它在维基百科
Additionally we add a breadth first search algorithm. It is described in Wikipedia
为简化该算法的实现，我们在节点上添加了已访问"标志.
To ease up the implementation of that algortuhm we a a "visited" flag to the node.
请参见下面的代码:
#include <sstream>
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <iomanip>
#include <numeric>
#include <algorithm>
#include <queue>
std::istringstream textFileStream(R"#(peach
peace
place
plane
plans
plays
slays
stays
stars
sears
years
yearn
)#");
using Vertex = std::string;
using Edge = std::vector<size_t>;
// One node in a graph
struct Node
{
// The Vertex is a std::string
Vertex word{};
// The edges are the index of the neighbour nodes
Edge neighbour{};
// For Breath First Search
bool visited{ false };
// Easy input and output
friend std::istream& operator >> (std::istream& is, Node& n) {
n.neighbour.clear();
std::getline(is, n.word);
return is;
}
friend std::ostream& operator << (std::ostream& os, const Node& n) {
os << std::left << std::setw(25) << n.word << " --> ";
std::copy(n.neighbour.begin(), n.neighbour.end(), std::ostream_iterator<int>(os, " "));
return os;
}
};
// The graph
struct UndirectedGraph
{
// Contains a vector of nodes
std::vector<Node> graph;
// build adjacenies
void build();
// Find Path
bool checkForPathFromStartToEnd(size_t start, size_t end);
bool checkForPath() {bool result = false;if (graph.size() > 1) {size_t s = graph.size() - 2;size_t e = s + 1;result = checkForPathFromStartToEnd(s, e); }return result; }
// Easy input and output
friend std::istream& operator >> (std::istream& is, UndirectedGraph& ug) {
ug.graph.clear();
std::copy(std::istream_iterator<Node>(is), std::istream_iterator<Node>(), std::back_inserter(ug.graph));
return is;
}
friend std::ostream& operator << (std::ostream& os, const UndirectedGraph& ug) {
size_t i{ 0 };
for (const Node& n : ug.graph)
os << std::right << std::setw(4) << i++ << ' ' << n << '\n';
return os;
}
};
// Distance between 2 strings
size_t levensthein(const std::string& string1, const std::string& string2)
{
const size_t lengthString1(string1.size());
const size_t lengthString2(string2.size());
if (lengthString1 == 0) return lengthString2;
if (lengthString2 == 0) return lengthString1;
std::vector<size_t> costs(lengthString2 + 1);
std::iota(costs.begin(), costs.end(), 0);
for (size_t indexString1 = 0; indexString1 < lengthString1; ++indexString1) {
costs[0] = indexString1 + 1;
size_t corner = indexString1;
for (size_t indexString2 = 0; indexString2 < lengthString2; ++indexString2) {
size_t upper = costs[indexString2 + 1];
if (string1[indexString1] == string2[indexString2]) {
costs[indexString2 + 1] = corner;
}
else {
const size_t temp = std::min(upper, corner);
costs[indexString2 + 1] = std::min(costs[indexString2], temp) + 1;
}
corner = upper;
}
}
size_t result = costs[lengthString2];
return result;
}
// Build the adjacenies
void UndirectedGraph::build()
{
// Iterate over all words in the graph
for (size_t i = 0; i < graph.size(); ++i)
// COmpare everything with everything (becuase of symmetries, omit half of comparisons)
for (size_t j = i + 1; j < graph.size(); ++j)
// Chec distance of the 2 words to compare
if (levensthein(graph[i].word, graph[j].word) < 2U) {
// And store the adjacenies
graph[i].neighbour.push_back(j);
graph[j].neighbour.push_back(i);
}
}
bool UndirectedGraph::checkForPathFromStartToEnd(size_t start, size_t end)
{
// Assume that it will not work
bool result = false;
// Store intermediate tries in queue
std::queue<size_t> check{};
// Set initial values
graph[start].visited = true;
check.push(start);
// As long as we have not visited all possible nodes
while (!check.empty()) {
// Get the next node to check
size_t currentNode = check.front(); check.pop();
// If we found the solution . . .
if (currentNode == end) {
// The set resultung value and stop searching
result = true;
break;
}
// Go through all neighbours of the current node
for (const size_t next : graph[currentNode].neighbour) {
// If the neighbour node has not yet been visited
if (!graph[next].visited) {
// Then visit it
graph[next].visited = true;
// And check following elements next time
check.push(next);
}
}
}
return result;
}
int main()
{
// Get the filename from the user
std::cout << "Enter Filename for file with words:\n";
std::string filename{};
//std::cin >> filename;
// Open the file
//std::ifstream textFileStream(filename);
// If the file could be opened . . .
if (textFileStream) {
// Create an empty graph
UndirectedGraph undirectedGraph{};
// Read the complete file into the graph
textFileStream >> undirectedGraph;
Node startWord{}, targetWord{};
std::cout << "Enter start word and enter target word\n"; // teach --> learn
std::cin >> startWord >> targetWord;
// Add the 2 words at the and of our graph
undirectedGraph.graph.push_back(startWord);
undirectedGraph.graph.push_back(targetWord);
// Build adjacency graph, including the just added words
undirectedGraph.build();
// For debug purposes: Show the graph
std::cout << undirectedGraph;
std::cout << "\n\nMorph possible? --> " << std::boolalpha << undirectedGraph.checkForPath() << '\n';
}
else {
// File could not be found or opened
std::cerr << "Error: Could not open file : " << filename;
}
return 0;
}
请注意:尽管我已经实现了要求输入文件名的功能，但在本示例中并未使用它.我从istringstream阅读.您需要稍后删除istringstream并在现有语句中添加注释.
Please note: Although I have implemented asking for a file name, I do not use it in this example. I read from a istringstream. You need to delete the istringstream later and comment in the existing statements.
关于讲师的要求:我没有使用任何STL/库/Boost搜索算法. (做什么用?在此示例中?)但是我当然使用其他C ++ STL容器.我不会重新发明轮子，而是想出一个新的向量"或队列.而且我绝对不会使用"new"或C-Style数组或指针算术.
Reagarding the requirements from the instructor: I did not use any STL/Library/Boost searching algorithm. (What for? In this example?) But I use of course other C++ STL container. I will not reinvent the wheel and come up with a new "vector" or queue. And I will definitely not use "new" or C-Style arrays or pointer arithmetic.
玩得开心！
对其他所有人:对不起:我无法抗拒编写代码. .
And to all others: Sorry: I could not resist to write the code . . .
这篇关于使用图的字符串搜索算法? C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
