1

I'm currently teaching myself about algorithms and about different problems that are interesting in CS. For an example if I wanted to solve the graph coloring problem with a greedy algorithm (e.g. choose what's best at the moment) and ensure that I have the correct solution, then I'd basically have to go through the graph more than one time, if I'm correct? Because choosing what's best at the moment is generally not optimal and might give wrong results.

To be more specific, I'd actually want to answer the decision problem: Is the graph G colorable with N colors? with a greedy algorithm, and the answer certainly needs to be correct.

So are there any example algorithms in pseudo code out there - or can I get a clue how I can make sure that I give the correct answer with this greedy algorithm?

Thanks in advance! I appreciate any reply

4

1 回答 1

1

据我了解，对于这样的问题，贪婪可能并不总是给出正确的解决方案，因为图可能包含循环，并且您可能不知道节点的某些边，直到您将空间减少到几个节点并且您留下不兼容颜色。对此的基本解决方案是回溯算法。在这种情况下，如果您可以将此问题简化为另一个具有贪心解决方案的 NP 问题，则可能在这种情况下使用贪心，但据我所知，我不知道有一个问题。

于 2013-11-05T22:33:09.110 回答