Re: Problem on an nxn grid

It has taken me days to understand the equivalent of
"See Spot Run" in the vocabulary of Graph Theory.
Sparing everyone the litany of that journey...

Thanks very much to every poster, especially Chip,
Asinops and Robert Israel, for their help.

The problem is a "maximum-weight matching" with n up to
around 300. Does there exist code (or better, pseudo-code)
to solve this? It could be argued that Chapter 5.3 of
Gibbons's "Algorithmic Graph Theory" gives a pseudo-code
for the Edmonds algorithm, but it is couched in, er,
Graphic, language. As, for the purposes of this discussion,
a lukewarm mathematician, and a lukewarm coder, it looks
daunting. Indeed, I have mined google, and although there
seems to be something approaching pseudo- code for related
problems (such as the Stable Roommate Problem) and code for
parts of the Edmonds algorithm (such as the Hungarian
algorithm), I could not find code or pseudo-code for the
whole kahuna, an algorithm which solves the maximum-weight
matching problem in polynomial time. Maybe I haven't looked
in the right places. But an email from one of you confirms:
no readily- available code.

I'm guessing that the reason will be that it is "too easy".
Too easy a subject for a degree thesis, that is.

Anyway, if somebody can point me to pseudo-code, I'd
appreciate it.

In a separate post, I will put forward an idea that might
not reduce the big-O Order of working this through by brute
force, but might reduce the real-world CPU time in cases
where the values (weights) are not overly close to each
other.

--
Jonathan Berry


.

Relevant Pages

  • Re: pseudo code v/s algorithm
    ... insert your language here) than code. ... There is absolutely no difference between algorithm and code, ... If I have an implementation or pseudo-code it cannot be ... Turing Machine or lambda-calculus in it, modulo the infinite memory ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... the lack of formalism and precision. ... Pseudo-code is necessarily more ... ambiguous than any formally specified programming language. ... formal algorithm from it, and the risks that your pseudocode is ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... Algorithm is like a thought. ... insert your language here) than code. ... Pseudo-code is just an informal way to express such a mathematical ... Turing Machine or lambda-calculus in it, modulo the infinite memory ...
    (comp.programming)
  • Re: pseudo code v/s algorithm
    ... Pseudo-code is necessarily more ... ambiguous than any formally specified programming language. ... Lisp is a forty-year old language that has hardly ever been used to ... pseudo-code is as good a starting point as the algorithm itself. ...
    (comp.programming)
  • Re: A weird requirement - unable to think of anything...
    ... This is prior-art for graph theory, ... You could program that as a sparse matrix, or as a real matrix in a 2D ... However, the algorithm you select will determine the data representation, ...
    (comp.programming)