Wish me luck...

[kmj]

I have to give a half hour presentation tonight for my AI class. It's on The Vacationing Student Problem, which I'll post some stuff for later. I know the stuff pretty well, I just have to keep my head clear, communicate well, and try not to blurt out the whole thing in 10 minutes. http://www.linuxnewbie.org/ubb/smile.gif

[YaRness]

that the one where you hafta go to cities and not repeat your path or something?

anyway the name sounds familiar. my ai prof was my advisor too, she rawked.

i hate comp sci classes where you hafta like, talk or write papers. at least that's subject-related. one of my classes (data structures or something) was made writing-intensive by the prof by adding essays and argument questions that weren't directly related to the subject. i did get him once good by exhaustively answering a question he posed for a 2-3 page paper in one paragraph (i got a 93/100 for it http://www.linuxnewbie.org/ubb/biggrin.gif ).

------------------
"Assembly of Japanese bicycle require great peace of mind."
Registered Linux User #188285 http://counter.li.org/
------------------

[Glaurung]

Is it something like "the travelling salesman's problem"?

[kmj]

<Homer Simpson>
Mmmm. Theory... : http://www.linuxnewbie.org/ubb/biggrin.gifrool, Drool::
</Homer Simpson>

It's a variant that I thought up*. Basically, you attempt to make each arc in your path be as close to some target value, instead of trying to minimize the sum of all the arc values. I'll post all my stuff when I get done, and maybe after i take a nice week's vacation.

*I may not have been the first to come up with it, but I haven't seen it anywhere else.

[kmj]

The presentation went pretty well; he'll be grading mostly on the project and report, though. As a bonus, there'll be a question from each of the presentations (there were 6, on for each grad student) on the final, so I'll get at least one question right! I've got the presentation in ppt and the report in doc, and a tar.gz of the code and examples. (I was too lazy to do latex and xfig! If anyone's that interested, I can easily make a postscript version...) The code is pathetic; I didn't have time to clean it up, or strip it down. I know there are parts that can be more efficient. I'll post it soon, regardless of interest. http://www.linuxnewbie.org/ubb/smile.gif

[Strike]

Originally posted by kmj:
(I was too lazy to do latex and xfig! If anyone's that interested, I can easily make a postscript version...)

/me nods

Yeah, I'd be interested. Even if the theory itself is too over my head or out of my realm of interest, I can probably learn a LaTeX trick or two if I see some cool formatting that I like. http://www.linuxnewbie.org/ubb/smile.gif

[kmj]

Originally posted by Strike:
/me nods

Yeah, I'd be interested. Even if the theory itself is too over my head or out of my realm of interest, I can probably learn a LaTeX trick or two if I see some cool formatting that I like. http://www.linuxnewbie.org/ubb/smile.gif



Well, I'd just take my ppt file and make it a .ps, so yo can open it w/ ghostview, so there'd be no .tex document (raw latex). The theory is very basic, I think. I've got the program up at www.cs.rit.edu/~kmj9907/VSP.tar.gz (http://www.cs.rit.edu/~kmj9907/VSP.tar.gz)

There's no readme, cuz I'm an idiot and I forgot to make one, so if anyone checks it out and can't figure it out, just ask.

Basically, just run make to make the classes, then java vsp [cityfile.vsp]. Be forewarned, it ain't pretty to behold, and if the input isn't as expected, it probably won't work at all.

If you're interested in latex, though, let me know. I've got a link to all the examples you'll need. somewhere in http://www.cs.rit.edu/~pga
edit: just checked, the link is on that page, along with a bunch of other cool stuff. He's an awesome Prof. for anyone else who may ever happen to take classes at RIT.

[This message has been edited by kmj (edited 14 November 2000).]

[Dru Lee Parsec]

Well, I hope I'm not too late but

GOOD LUCK! http://www.linuxnewbie.org/ubb/biggrin.gif

Do you use Euler paths to calculate the route?

[kmj]

Originally posted by Dru Lee Parsec:
Well, I hope I'm not too late but

GOOD LUCK! http://www.linuxnewbie.org/ubb/biggrin.gif

Do you use Euler paths to calculate the route?
Nah; it's really basic. I just do a depth first search. The child-production routine is such that only valid child nodes (I did the NP-complete version) will get looked at, so once you reach a depth of n, where n is the number of cities, you have that many cities in the list, and you're done.

I don't know if I specified the problem anywhere, so I guess I'll do it now. Basically, with the VSP, you're given some target value, and instead of minimizing the sum of all the arcs for a full cycle through the set of cities, you attempt to make each arc get as close to that target value. (An arc is a connection from one city to another, could be in units of time, distance, cost, etc.) The NP-Complete gives you a target T and a max allowable error E, so the solution would be any one of the paths where for each arc in the path:
|V - T| <= E, where V is the value of that arc.

The NP-hard version uses the same formula, for each V, |V - T| <= E, except you're not given E, and you have to find the single route with the Absolute minimum worst-case E. (the route who's highest E value is less than or equal to any other routes highest E). I didn't solve that, but I think it wouldn't be too bad if you just did a simple best first search where the heuristic value is the worst-case E for that path.